SHARE
TWEET

Untitled

a guest Sep 14th, 2019 219 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top