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

Top