daily pastebin goal
49%
SHARE
TWEET

RSA Encryption/ Decryption

RootOfTheNull Aug 14th, 2018 351 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: 2016-12-03 11:16:39
  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
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