 # RSA Encryption/ Decryption

Aug 14th, 2018
3,688
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 getPrime, inverse
9. import binascii
10.
11. '''
12. This Python code tries to illustrate how RSA is done at a basic level.
13. '''
14.
15.
16. # At RSA's core, there are two PRIME factors, p and q.
17. # With this code, I just generate two large random prime numbers.
18. # p and q are typically NOT given to you in an RSA challenge.
19. bits_size = 256
20. p = getPrime( bits_size )
21. q = getPrime( bits_size )
22.
23.
24. # These two prime factors multiply to create n, which is "the modulus".
25. # n is typically GIVEN to you in an RSA challenge.
26. n = p * q
27.
28.
29. # The plaintext is typically referred to as m. Since we are working
30. # with numbers and math, we treat the string information as hex.
31. # Obviously this is NEVER given to you in an RSA challenge.
32. m = "This is the clear text message."
33. m = binascii.hexlify(m)
34. m = int(m, 16)
35.
36.
37. # Another value, called e, is "the exponent".
38. # Both e and n make up "the public key", which is meant to be common
39. # knowledge. This is why typically n and e are BOTH GIVEN in an RSA challenge.
40. # Typcially, e is 65537, which is 0x10001 in hex
41. e = 0x10001
42.
43.
44. # The ciphertext, c, is created by this ENCRYPTION formula here.
45. #    c = ( m ^ e ) % n
46. # See how e is the exponent and n is the modulus?
47. # That is how the ENCRYPTION takes place.
48. # Typically you are given the c in an RSA challenge and it is your task
49. # to DECRYPT it to the m value, the plaintext.
50. c = pow( m, e, n )
51.
52.
53. # Now how do we decrypt? We need "the private key"....
54. # We call this d in RSA. Thanks to some handy mathematical functions,
55. # you can find "Euler's Totient", or "the Phi function" of a number.
56. # This is 'the number of numbers that are less than a certain number and share
57. # a common denominator with that certain number'.
58. # I know that is hard to wrap your mind around here, but thankfully it is MUCH
59. # easier for a prime number. For a prime number, it is simply that number minus 1!
60.
61. # So, if you are given n, what you need to do is find the factors of n.
62. # Like we've seen, this is typically p and q. So, can we find the phi function
63. # of n? Well, n is prime, and so are its factors, p and q, so phi should just be:
64. phi = ( q - 1 ) * ( p - 1 )
65.
66.
67. # Now, we can kind of unravel that modular arithmetic that was done during the
68. # ENCRYPTION formula. We can find the private key, d, with the MODULAR INVERSE,
69. # of e and phi.
70. # I use a module to do this that is reworked to use Trey's function
71. #     https://github.com/JohnHammond/primefac_fork
72. d = inverse( e, phi )
73.
74. # Now, we can do a similar thing like before, but this time for DECRYPTION.
75. #        m = ( c ^ d ) % n
76. # This time we raise to our private key as an exponent, but still take the modulus.
77. # And we have successfully decrypted RSA!
78. m = pow( c, d, n )
79. print repr(binascii.unhexlify(hex(m)[2:-1]))
RAW Paste Data