diff options
author | Malfurious <m@lfurio.us> | 2021-11-28 02:06:23 -0500 |
---|---|---|
committer | Malfurious <m@lfurio.us> | 2021-11-28 02:06:23 -0500 |
commit | 6f3856705c226557ff64bf2c24cafad55844c562 (patch) | |
tree | 49386b5c5e3ef2bad118ad05e213454c9880e6ce /docs | |
parent | adeca0ca315928384873c15b25a884065b9cb1cb (diff) | |
download | lib-des-gnux-6f3856705c226557ff64bf2c24cafad55844c562.tar.gz lib-des-gnux-6f3856705c226557ff64bf2c24cafad55844c562.zip |
Commit notes from Killer Queen CTF 2021
Signed-off-by: Malfurious <m@lfurio.us>
Diffstat (limited to 'docs')
-rw-r--r-- | docs/crypto/rsa.txt | 43 |
1 files changed, 43 insertions, 0 deletions
diff --git a/docs/crypto/rsa.txt b/docs/crypto/rsa.txt new file mode 100644 index 0000000..a047f07 --- /dev/null +++ b/docs/crypto/rsa.txt @@ -0,0 +1,43 @@ +Brief summary of RSA algorithm / crypto system +---------------------------------------------- +# https://www.cs.utexas.edu/~mitra/honors/soln.html + +Choose 2 large, random prime numbers, p and q. + +n = p * q +phi = (p-1) * (q-1) + +Choose e, such that `1 < e < phi` and e and phi are coprime (*) (**) (***) +Compute d, such that `e * d mod phi == 1` (****) + +Public key = (e, n) +Private key = (d, n) + +cyphertext = plaintext ^ e mod n +plaintext = cyphertext ^ d mod n + + +(*) It is important for e and phi to be coprime, to prevent ambiguous + decryption. See https://crypto.stackexchange.com/questions/12255/ + +(**) A very common value for e is (the prime) 65537 + +(***) RSA can become more vulnerable to cracking with low values of e. + See https://crypto.stackexchange.com/questions/6713/. + TODO: Explain the attack here. + +(****) Calculate d using modular inverse (see below...) + + + +Python tips +----------- +Implementations for fast modular exponentiation and modular inverse already +exist in Python, via the pow() function. + +pow() supports a third argument, which is the modulus value: pow(b, e, n). + +To perform fast mod expo for encryption, use pow(plaintext, e, n) + ... for decryption, use pow(cyphertext, d, n) + +To calculate mod inverse, use pow(e, -1, phi). |