Guest User

Untitled

a guest
Sep 14th, 2019
1,309
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # This piece of code observe's Robert Grant's claim that prime
  2. # factors of RSA public keys can be found from the repeating decimal
  3. # inverse of semi-prime.
  4.  
  5. # The method was determined from Grant's Instagram account:
  6. #   https://www.instagram.com/p/B2HwOirnHH2/?utm_source=ig_web_copy_link
  7.  
  8. # To test this claim we
  9.  
  10. # 1. Create two primes
  11. # 2. Multiply the two primes to produce a semi-prime
  12. # 3. Take inverse of the semi-prime
  13. # 4. Search the two primes for one or both of the factors.
  14. # 5. The results will either be:
  15. #   a)     every repeating inverse of semi-prime will contain both primes <-- Allows breaking RSA if efficiency is good enough.
  16. #   b) NOT every repeating inverse of semi-prime will contain both primes <-- Does not allow breaking RSA reliably.
  17.  
  18. # In order to prove Grant's factoring algorithm valid, the method must
  19. # work on all semi-primes. Otherwise it's just a coincidence, like how
  20. # the number Pi happens to contain patterns like 0123456789 at position
  21. # 17,387,594,880.
  22.  
  23. from decimal import Decimal, getcontext
  24. from random  import SystemRandom
  25. from typing  import Tuple
  26.  
  27.  
  28. def generate_random_prime_smaller_than(n) -> int:
  29.     """Returns a random prime smaller than n.
  30.  
  31.     Based on
  32.         https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n/3035188#3035188
  33.     """
  34.     sieve = [True] * n
  35.  
  36.     for i in range(3,int(n**0.5)+1,2):
  37.         if sieve[i]:
  38.             sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
  39.  
  40.     list_of_primes = [2] + [i for i in range(3,n,2) if sieve[i]]
  41.     random_prime   = SystemRandom().choice(list_of_primes)
  42.  
  43.     return random_prime
  44.  
  45.  
  46. def multiply_prime_numbers(first_prime:  int,
  47.                            second_prime: int
  48.                            ) -> int:
  49.     """Create semi-prime, i.e. multiply two prime numbers.
  50.  
  51.    The semi-prime is the RSA public key.
  52.    """
  53.     return first_prime * second_prime
  54.  
  55.  
  56. def get_inverse_of_semi_prime(semi_prime: int) -> Decimal:
  57.     """Take inverse of semi-prime.
  58.  
  59.    The inverse should contain both prime number factors of the semi-prime.
  60.    """
  61.     return Decimal(1) / Decimal(semi_prime)
  62.  
  63.  
  64. def get_period_of_inverse_of_semi_prime(semi_prime):
  65.     """Find length of period in inverse of semi-prime.
  66.  
  67.    The period defines the length of numbers where the prime factors of
  68.    the public key can be.
  69.  
  70.    Borrowed from https://www.geeksforgeeks.org/find-length-period-decimal-value-1n/
  71.    """
  72.     remainder = 1  # Initialize remainder
  73.     for i in range(1, semi_prime + 2):
  74.         remainder = (10 * remainder) % semi_prime
  75.  
  76.     # Store (n+1)th remainder
  77.     d = remainder
  78.  
  79.     # Count the number of remainders before next
  80.     # occurrence of (n+1)'th remainder 'd'
  81.     count     = 0
  82.     remainder = (10 * remainder) % semi_prime
  83.     count    += 1
  84.     while remainder != d:
  85.         remainder = (10 * remainder) % semi_prime
  86.         count    += 1
  87.     return count
  88.  
  89.  
  90. def search_primes_in_inverse_of_semi_prime(inverse_of_semi_prime: Decimal,
  91.                                            first_prime:           int,
  92.                                            second_prime:          int
  93.                                            ) -> Tuple[int, int]:
  94.     """Return True if inverse of semi-prime contains both prime factors."""
  95.  
  96.     inverse_of_semi_prime_string = str(inverse_of_semi_prime)
  97.  
  98.     position_of_first_prime  = inverse_of_semi_prime_string.find(str(first_prime))
  99.     position_of_second_prime = inverse_of_semi_prime_string.find(str(second_prime))
  100.  
  101.     return position_of_first_prime, position_of_second_prime
  102.  
  103.  
  104. def found_both_prime_factors(first_prime:  int,
  105.                              second_prime: int,
  106.                              semi_prime:   int) -> True:
  107.     """Find prime factors of semi-prime from the inverse of.
  108.  
  109.    If prime factors were found, return True
  110.    """
  111.  
  112.     # Step 0: Determine the required precision of the decimals
  113.     period_length     = get_period_of_inverse_of_semi_prime(semi_prime)
  114.     getcontext().prec = period_length + 10
  115.  
  116.     # Step 1: Get the inverse of the semi-prime
  117.     inverse_of_semi_prime = get_inverse_of_semi_prime(semi_prime)
  118.  
  119.     if debug:
  120.         print(f"\nDEBUG: Inverse of the semi prime has period of {period_length} and looks as follows:")
  121.         print('       ' + str(inverse_of_semi_prime))
  122.         print('')
  123.  
  124.     # Step 2: See if the prime factors are in the inverse of the semi-prime.
  125.     position_first, position_second = search_primes_in_inverse_of_semi_prime(inverse_of_semi_prime, first_prime, second_prime)
  126.  
  127.     found_first_prime_factor  = position_first  != -1
  128.     found_second_prime_factor = position_second != -1
  129.  
  130.     if debug:
  131.         if found_first_prime_factor:
  132.             print(f"DEBUG: Found the first prime factor {first_prime} in position {position_first}")
  133.         else:
  134.             print(f"DEBUG: Did not find the first prime factor {first_prime} in the inverse of the semi-prime.")
  135.  
  136.         if found_second_prime_factor:
  137.             print(f"DEBUG: Found the second prime factor {second_prime} in position {position_second}")
  138.         else:
  139.             print(f"DEBUG: Did not find second prime factor {second_prime} in the inverse of the semi-prime.")
  140.  
  141.     return found_first_prime_factor or found_second_prime_factor
  142.  
  143.  
  144. debug = False
  145.  
  146. def main():
  147.     PRIME_UPPER_LIMIT           = 500
  148.     NUMBER_OF_TESTS_TO_RUN      = 1000
  149.     used_prime_tuples           = []
  150.     prime_pair_repeat_threshold = 10
  151.  
  152.     for _ in range(NUMBER_OF_TESTS_TO_RUN):
  153.  
  154.         # RSA private key generation
  155.         prime_pairs_repeated = 0
  156.         while True:
  157.             first_prime  = generate_random_prime_smaller_than(PRIME_UPPER_LIMIT)
  158.             second_prime = generate_random_prime_smaller_than(PRIME_UPPER_LIMIT)
  159.  
  160.             if (first_prime, second_prime) not in used_prime_tuples:
  161.                 used_prime_tuples.append((first_prime, second_prime))
  162.                 break
  163.             else:
  164.                 prime_pairs_repeated += 1
  165.                 if prime_pairs_repeated >= prime_pair_repeat_threshold:
  166.                     print("Running out of unique prime tuples for private keys. Exiting.")
  167.                     exit()
  168.  
  169.         # RSA public key generation
  170.         semi_prime = multiply_prime_numbers(first_prime, second_prime)
  171.  
  172.         if debug:
  173.             print(f"\nDEBUG: Upper limit of generated primes for private key is {PRIME_UPPER_LIMIT}")
  174.             print(f"\nDEBUG: Private key is {(first_prime, second_prime)}")
  175.             print(f"DEBUG: Public  key is {semi_prime}")
  176.  
  177.         if not found_both_prime_factors(first_prime, second_prime, semi_prime):
  178.             print(f"Grant's \"factoring method\" FAILS when primes are {(first_prime, second_prime)}")
  179.  
  180.  
  181. if __name__ == '__main__':
  182.     main()
  183.  
  184. # Example output:
  185.  
  186. # Grant's "factoring method" FAILS when primes are (151, 241)
  187. # Grant's "factoring method" FAILS when primes are (53, 271)
  188. # Grant's "factoring method" FAILS when primes are (211, 449)
  189. # Grant's "factoring method" FAILS when primes are (41, 53)
  190. # Grant's "factoring method" FAILS when primes are (271, 229)
  191. # Grant's "factoring method" FAILS when primes are (137, 17)
  192. # Grant's "factoring method" FAILS when primes are (271, 239)
  193. # Grant's "factoring method" FAILS when primes are (5, 41)
  194. # Grant's "factoring method" FAILS when primes are (151, 101)
  195. # Grant's "factoring method" FAILS when primes are (137, 389)
  196. # Grant's "factoring method" FAILS when primes are (463, 67)
  197. # Grant's "factoring method" FAILS when primes are (281, 463)
  198. # Grant's "factoring method" FAILS when primes are (211, 241)
  199. # Grant's "factoring method" FAILS when primes are (199, 331)
  200. # Grant's "factoring method" FAILS when primes are (197, 127)
  201. # Grant's "factoring method" FAILS when primes are (211, 353)
  202. # Grant's "factoring method" FAILS when primes are (349, 101)
  203. # Grant's "factoring method" FAILS when primes are (101, 29)
  204. # Grant's "factoring method" FAILS when primes are (151, 271)
  205. # Grant's "factoring method" FAILS when primes are (127, 197)
  206. # Grant's "factoring method" FAILS when primes are (127, 193)
  207. # Grant's "factoring method" FAILS when primes are (37, 23)
  208. # Grant's "factoring method" FAILS when primes are (271, 101)
  209. # Grant's "factoring method" FAILS when primes are (13, 3)
  210. # Grant's "factoring method" FAILS when primes are (271, 241)
  211. # Grant's "factoring method" FAILS when primes are (239, 107)
  212. # Grant's "factoring method" FAILS when primes are (3, 127)
  213. # Grant's "factoring method" FAILS when primes are (353, 271)
  214. # Grant's "factoring method" FAILS when primes are (241, 37)
  215. # Grant's "factoring method" FAILS when primes are (73, 271)
  216. # Grant's "factoring method" FAILS when primes are (449, 137)
  217. # Grant's "factoring method" FAILS when primes are (157, 11)
  218. # Grant's "factoring method" FAILS when primes are (229, 101)
  219. # Grant's "factoring method" FAILS when primes are (241, 137)
  220. # Grant's "factoring method" FAILS when primes are (241, 401)
  221. # Grant's "factoring method" FAILS when primes are (41, 13)
  222. # Grant's "factoring method" FAILS when primes are (67, 13)
  223. # Grant's "factoring method" FAILS when primes are (139, 47)
  224. # Grant's "factoring method" FAILS when primes are (2, 13)
  225. # Grant's "factoring method" FAILS when primes are (13, 127)
  226. # Grant's "factoring method" FAILS when primes are (163, 109)
  227. # Grant's "factoring method" FAILS when primes are (239, 53)
  228. # Grant's "factoring method" FAILS when primes are (353, 109)
  229. # Grant's "factoring method" FAILS when primes are (17, 101)
  230. # Grant's "factoring method" FAILS when primes are (101, 499)
  231. # Grant's "factoring method" FAILS when primes are (401, 251)
  232. # Grant's "factoring method" FAILS when primes are (463, 239)
  233. # Grant's "factoring method" FAILS when primes are (101, 53)
  234. # Grant's "factoring method" FAILS when primes are (239, 19)
  235. # Grant's "factoring method" FAILS when primes are (397, 101)
  236. # Grant's "factoring method" FAILS when primes are (11, 271)
  237. # Grant's "factoring method" FAILS when primes are (2, 101)
  238. # Grant's "factoring method" FAILS when primes are (103, 101)
  239. # Grant's "factoring method" FAILS when primes are (463, 281)
  240. # Grant's "factoring method" FAILS when primes are (311, 211)
  241. # Grant's "factoring method" FAILS when primes are (193, 353)
  242. # Grant's "factoring method" FAILS when primes are (353, 257)
  243. # Grant's "factoring method" FAILS when primes are (311, 239)
  244. # Grant's "factoring method" FAILS when primes are (113, 127)
  245. # Grant's "factoring method" FAILS when primes are (331, 239)
  246. # Grant's "factoring method" FAILS when primes are (5, 101)
  247. # Grant's "factoring method" FAILS when primes are (233, 349)
  248. # Grant's "factoring method" FAILS when primes are (17, 113)
  249. # Grant's "factoring method" FAILS when primes are (257, 353)
  250. # Grant's "factoring method" FAILS when primes are (241, 223)
  251. # Grant's "factoring method" FAILS when primes are (19, 13)
  252. # Grant's "factoring method" FAILS when primes are (127, 11)
  253. # Grant's "factoring method" FAILS when primes are (271, 11)
  254. # Grant's "factoring method" FAILS when primes are (233, 449)
  255. # Grant's "factoring method" FAILS when primes are (23, 137)
RAW Paste Data