 # 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:
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 =  + [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.
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