Sorceress

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