I love cryptography, and I especially love the math behind public-key crypto and its (relative) simplicity when distilled. However, I still find myself losing a firm mental grasp on the entirety of the cryptosystem if I haven’t thought about it in a while. Since I try to keep fresh with Python even though I don’t use it every day, I figured writing toy implementations of Diffie-Hellman and RSA in Python would be a good way to refresh both of those areas.

Here’s the sample output of a run of the DH demo:

generator g = 2
safe prime p = 964738809dbecd4bcb9ba1d18de0f5a6fbd595383c2dbe460f8dfd6dea62d2a6bca4016806c788e89872e888137d767030c72a17ac7d6cc33e5b44a9c17ad32412656ac0770829412b502dc6010545cc26043b55bbccf7946de94c0a4c1c0386a255d9101a235e0427aefb003cc7a6e64c0860349fc6e220fc7fef110a60ad727e6af317cefbeab4216e0f76dadb816cfdf2cd90549340dc7eef977a7c3133f854088b0390a4d55d6244bc2f8f532401f6d224379b475fd1e30e4de0e52fba9273b742773dcea2c427804d3273d2f2cbcfb4d5deeb80c05282563a37777cabb4c0de696f41f622f6e59b613925ba6ec21b5b380d42f36aa6997fb6f4efcc5b4b
random secret a = 5d089da62d878fde8749d1f1bd366d789f68c453c955076e5d7d016b3b5a1b70
random secret b = 5c81b7ab27b1c7256b8aebaa5817ff2f79e23a3db7ae521633136226bfd11cac

g ^ a mod p = 8aa9704ee8f4b069b65afa1e2515ee0177cf547420d78cd14e52ef07162a2159f04406eb88d2f8019dc0e37a4fb17c42bd93caf143436ff1f229f6a909fa015c43774ec066fed8f8d699a31f7b8c207d700c3f5c4c1e7aa50afb80b9233cfa5b00c4f0b0aad7c011affef7df650bdf281d48961fd2acb2ad96d6e1ea19e910ee793f4103262d68e81dfaaf60b7e27e69d41c7d5729231e2c118d533093aadbc6b0fa983e5f28f0a92a1df4370105643940f67db1584d06d8f4dff7a14c91186587c6a7663505eefe42274a9b2b51faf5ac3ce1653f0ff016b1abd8217652b5e3916d519d3087bffb28ea3c8b69b8e496f0aa05c0142876e0a716b98fe4ae6c03
g ^ b mod p = 600008e084d3234eb57996affb5a5e15cea6017c3af118dca59b7aae5476ccba8b3dbe2051a7340240894dcf44ba4705052e55668674bdc3dab10332e7bd9061dbbe7a3430c0c891e0a651bd6778e791fcc95a5c6ae952660eea9b6fb65e503c9d7b94f7355b51872380b2e4fcbc94f0fcfa83e437e677d5796ac016c92f651391cad83db247cd12ecdb703df17a35efd93141d8219420be02e4a941820a4eaa2eb1ddda992589d83650ce22c8bd3db4b7b062eb66abd6dab6181002b95b6daa383b56ae37c8a378d71b6ca88b6099c3313d6b3e5299b5960b6eafea2761ca8807138b773b63035fe429178e52bd5656c7e278eac85e6d952de47d24e3c6cab5

alice derives premaster secret via (g^b)^a mod p: 7d9ca5dc613b1f965d7adfa695d7d2a8aeeadc0a063d609ace20d92ceb504b7c9ca03196056f9d5dabe3a8a7a0161666322c9dc3b6521b05829d4ef3ff5b0db5ee04fdb4cc80052e82f0036d7414b84fdfd5687c2c95c118aa433a92c52c1124cb69082889ce4aac2cb8bfeb1657b59337c516c3db026e4bfdd343de2e2088a1109e63e6bfe5000351631465a808f2b1ede8ba7d36bd9e71511f5ad4e8e31550fd3ac15301c3e8f89cf710fa04722a26ea1080d631a857fcae69150712ab80a38df795920022195a7df2363962736653cfa7704343064eb693fa28dd7b718c31000301f41ae568700b48327b99602b12f53a9f8938ae56839273ff8dec0ddad6
bob derives premaster secret via (g^a)^b mod p: 7d9ca5dc613b1f965d7adfa695d7d2a8aeeadc0a063d609ace20d92ceb504b7c9ca03196056f9d5dabe3a8a7a0161666322c9dc3b6521b05829d4ef3ff5b0db5ee04fdb4cc80052e82f0036d7414b84fdfd5687c2c95c118aa433a92c52c1124cb69082889ce4aac2cb8bfeb1657b59337c516c3db026e4bfdd343de2e2088a1109e63e6bfe5000351631465a808f2b1ede8ba7d36bd9e71511f5ad4e8e31550fd3ac15301c3e8f89cf710fa04722a26ea1080d631a857fcae69150712ab80a38df795920022195a7df2363962736653cfa7704343064eb693fa28dd7b718c31000301f41ae568700b48327b99602b12f53a9f8938ae56839273ff8dec0ddad6

secrets match, and can be used to derive a session key for symmetric encryption

Here’s the code on GitHub.

Here’s a sample output of the RSA demo:

############ KEY GENERATION ############

generating a 256-bit modulus
random large prime p = 7c3235989ff4fa33daafc7c6cddfedc09463709d0c06cedcb79a71201ef2249d
random large prime q = 7905b80fe0c2a96cad933d3c4fa89dad8d9c55da48f51eba3441b728a4336a01

modulus n (p * q) = 3ab6819bfa172018e0f59665592b67402a5bf8cdfc5ef61f4c35013bccc7a8ca258e2f52c654170a131f7676c1facbfb3b394c17de306540e589fb2a4162269d

φ(n) = (p - 1) * (q - 1) = 3ab6819bfa172018e0f59665592b67402a5bf8cdfc5ef61f4c35013bccc7a8c9305641aa459c73698adc7173a472408d193985a0893477a9f9add2e17e3c9800

public/encryption exponent e (statically set) = 10001
private/decryption exponent d (modular inversion of e mod φ(n)) = 3a8f0f2457c2bae3b5739ce6469290afa1d00b8ebf38a37841d4d7ff21d6bd94b45e43ae2531ceb6a4a60b8dd0a59796636348d0fe27d37637add417cd857801

############ ENCRYPTION ############

enter text to encrypt (encoded length must be less than keysize): attack at dawn

encoded cleartext as integer m: 61747461636b206174206461776e

ciphertext (m ^ e mod n): 185de13c3735dd22fd173e76276921f52e8fd5653dcad619fb5db6fb26964ec1bb98f8bc941706075672ad879745124ddc9fdc6a0b5ec35fbda872384a4cdb1a

############ DECRYPTION ############

decrypted ciphertext as int (c ^ d mod n): 61747461636b206174206461776e
decrypted ciphertext: attack at dawn

And here’s the gist for that one.