• API
• FAQ
• Tools
• Archive
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:
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
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.

Top