daily pastebin goal
94%
SHARE
TWEET

RSA Chinese Remainder Theorem

RootOfTheNull Aug 14th, 2018 105 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env python
  2. # -*- coding: utf-8 -*-
  3. # @Author: john
  4. # @Date:   2016-08-25 14:33:10
  5. # @Last Modified by:   john
  6. # @Last Modified time: 2017-02-28 18:52:57
  7.  
  8. from Crypto.Util.number import *
  9. import binascii
  10. import sympy
  11.  
  12.  
  13. e = 3
  14.  
  15. bitsize = 512
  16.  
  17. n1 = n2 =n3 = 0
  18.  
  19. while ( ( sympy.gcd(n3,n2) !=  1 ) and ( sympy.gcd(n1,n2) !=  1 ) and ( sympy.gcd(n1,n2) !=  1 ) ):
  20.  
  21.     n1 = getPrime( bitsize )
  22.     n2 = getPrime( bitsize )
  23.     n3 = getPrime( bitsize )
  24.     # n4 = getPrime( bitsize )
  25.    
  26.  
  27. # print n1, n2, n3
  28. print "n1 = ", n1
  29. print "n2 = ", n2
  30. print "n3 = ", n3
  31. # print "n4 = ", n4
  32. # print sympy.gcd(n1,n2), sympy.gcd(n1,n3), sympy.gcd(n3,n2)
  33.  
  34. m = 'USCGA{the_chinese_remainder_theorem_is_so_cool}'
  35. m = binascii.hexlify(m)
  36. m = int(m, 16)
  37.  
  38. c1 = pow(m, e, n1)
  39. c2 = pow(m, e, n2)
  40. c3 = pow(m, e, n3)
  41. # c4 = pow(m, e, n4)
  42. print ""
  43.  
  44. print "c1 = ", c1
  45. print "c2 = ", c2
  46. print "c3 = ", c3
  47.  
  48. def chinese_remainder(n, a):
  49.     sum = 0
  50.     prod = reduce(lambda a, b: a*b, n)
  51.  
  52.     for n_i, a_i in zip(n, a):
  53.         p = prod / n_i
  54.         print "n_i", n_i
  55.         print "a_i", a_i
  56.         print "p", p
  57.         #sum += a_i * mul_inv(p, n_i) * p
  58.         sum += a_i * inverse(p, n_i) * p
  59.         print "sum", sum
  60.     return sum % prod
  61.  
  62. x = chinese_remainder([n1, n2, n3], [c1, c2, c3])
  63. # print x
  64.  
  65. # 1. Simple attack
  66. # m = sympy.root(x, e)
  67.  
  68. m = pow(sympy.E,  sympy.ln(x) / e )
  69.  
  70.  
  71. print "Trey's one sum", c1 * n2 * n3 * inverse( n2*n3, n1 )
  72. # # THIS IS THE CHINESE REMAINDER THEOREM IN ONE EQUATION ... FROM TREY
  73. # m = ( c1 * n2 * n3 * inverse( n2*n3, n1 ) + c2 * n1 * n3 * inverse( n1*n3, n2 ) + c3 * n1 * n2 * inverse( n1*n2, n3 ) ) % ( n1 * n2 * n3 )
  74. # print m == x
  75.  
  76. # print pow(10, sympy.ln(pow(m,e)))
  77.  
  78.  
  79. print ""
  80.  
  81. # print
  82.  
  83. try:
  84.     print hex(int(m))[2:-1].decode('hex')
  85. except:
  86.     print "Supposedly odd length string..."
  87.     print str("0"+ hex( int(m))[2:-1]).decode('hex')
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