# RSA factorisation demo

Mar 13th, 2021 (edited)
60
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. 'RSA factorisation demo
2. '---------------------------
3.
4. 'let's make some primes
5. DIM pr(4000) AS LONG
6. pr(0) = 2: N = 3:: jmax = 0: i = 0
7. WHILE i < 4000
8. IF pr(jmax) * pr(jmax) < N THEN jmax = jmax + 1
9. ok = 1
10. FOR j = 0 TO jmax
11. IF N MOD pr(j) = 0 THEN ok = 0: j = jmax
12. NEXT
13. IF ok = 1 THEN i = i + 1: pr(i) = N
14. N = N + 2
15. WEND
16. RANDOMIZE TIMER
17.
18. 'let's make some coprime semiprimes
19. DIM sp(7) AS LONG
20. FOR i = 0 TO 7
21. sp(i) = pr(i) * pr(16 - i)
22. NEXT
23.
24. 'and let's make two of these share a common factor, as might happen if the prime generating RNG has some bias.
25. i = INT(RND * 8): j = INT(RND * 7): IF j >= i THEN j = j + 1
26. k = INT(RND * 16 + 16)
27. sp(i) = pr(i) * pr(k)
28. sp(j) = pr(j) * pr(k)
29. PRINT "Our semiprimes:"
30. FOR i = 0 TO 7: PRINT sp(i);: NEXT: PRINT
31.
32. DIM bitmask AS LONG, Q0 AS _UNSIGNED _INTEGER64, Q1 AS _UNSIGNED _INTEGER64, Q AS _UNSIGNED _INTEGER64
33. 'Need to make all these variables 'bigints' for this to be more impressive... This is a very simple demo.
34.
35. 'Partition S into two half sets S0 and S1, via Hadamard basis vectors.
36. 'Q0 and Q1 are each the product of elements in the corresponding half set.
37. 'We need only log2(8)=3 gcd tests for these 8 semiprimes. So k runs from 0 to 2.
38.
39. 'In proper tests, we might have millions of keys scraped from web traffic.
40. 'If some are generated with bad RNGs, then there could be common prime factors
41. 'among them, which could be found with this algorithm, to factorise those keys.
42.
43. PRINT "Search for common factors:"
44. FOR k = 0 TO 2: bitmask = 2 ^ k
45. Q0 = 1: Q1 = 1
46. FOR i = 0 TO 7
47. IF (i AND bitmask) > 0 THEN Q0 = Q0 * sp(i) ELSE Q1 = Q1 * sp(i)
48. NEXT
49. 'Find Q = GCD(Q0,Q1)
50. IF Q0 < Q1 THEN Q = Q0: Q0 = Q1: Q1 = Q
51. WHILE Q0 > 0
52. Q = Q0: Q0 = Q1 MOD Q0: Q1 = Q
53. WEND
54. Q = Q1
55. IF Q > 1 THEN PRINT Q 'if we find a common prime, show it.
56. NEXT
57.
RAW Paste Data