β οΈBaby RSA Quiz
Author: @Gary#4657
What should we do?
A nice RSA warmup for you crypto nerds. If you are new to RSA, this challenge is for you :)
user@pc:~/Desktop$ nc challenge.nahamcon.com <port>
Welcome to the Baby RSA Quiz!
Choose Option 0 if you're asking yourself "what in the world is RSA?" or maybe want to run through the basics.
Choose Option 1 if you're comfortable with RSA, feel free to skip to the quiz
Choose Option 2 if Rivest, Shamir, or Adleman hurt your feelings, feel free to exit the program
/------------------------\
| Baby RSA MENU: |
| (0) Teach me some RSA! |
| (1) Skip to quiz |
| (2) Quit |
\------------------------/
Choice: 0
________________________________________________________________________________________________
RSA is a public-key (asymmetric) cryptosystem named after its creators: Ronald Rivest,
Adi Shamir, and Leonard Adleman). Because this is an assymetric system, there exists two keys:
a public key (shared openly) and a private key (kept secret). On the other hand, for a symmetric
cryptosystem like AES, a private key is shared between both parties. For our case, the sender
encrypts their message with the receiver's public key and the receiver decrypts the sender's
encrypted message with the private key corresponding to the public key used by the sender.
Press Enter to continue...
________________________________________________________________________________________________
Let's say Bob wants to send a message to Alice using this RSA encryption scheme. Bob needs
Alice's public key in order to encrypt his message and send it to Alice.
Bob Alice
/(... ,-"=-.
/ ,-(_`; . \
\ )_ _; n, e "='"=\ '
(\[_][_]) <======================= `@] @'| )
| L | ) ` ' ),-`
| \-_/ \^_, \,
| | ,(\,/ )`-.
An RSA public key is comprised of two integers: n and e
n: public modulus
e: public exponent
Press Enter to continue...
________________________________________________________________________________________________
Now Bob has the facilities to send Alice a message. Bob now sends the ciphertext (ct)
using his plaintext (pt) represented as an integer and Alice's public key such that:
ct = (pt)^e mod n.
Bob Alice
/(... ,-"=-.
/ ,-(_`; . \
\ )_ _; ct = (pt)^e mod n "='"=\ '
(\[_][_]) =======================> `@] @'| )
| L | ) ` ' ),-`
| \-_/ \^_, \,
| | ,(\,/ )`-.
Alice now has Bob's encrypted message and uses her private exponent (d) to decrypt
the message such that: pt = (ct)^d mod n.
An RSA private key is comprised of two integers: d and n
n: public modulus
d: private exponent
Press Enter to continue...
________________________________________________________________________________________________
Let's talk about the key generation of RSA and some of the properties of secure RSA. Typically,
secure RSA parameters includes the use of 2048-bit or 4096-bit prime numbers. If don't know how
big 2048/4096-bit values are give this a nice run in Python:
>>> from Crypto.Util.number import getPrime
>>> getPrime(2048)
Here is a rough outline of how RSA keys are generated:
- Generate prime number p
- Generate prime number q
- n = p*q
- Ξ»(n) = lcm(Ξ»(p), Ξ»(q)) = lcm(p-1, q-1)
- 1 < e < Ξ»(n) s.t. gcd(e, Ξ»(n)) = 1 (aka. e and Ξ»(n) are coprime)
- the most common value for e is 2^16 + 1 = 65537
- the fastest value for e is 3, but this isn't totally secure in some settings.
- calculate d s.t. d*e = 1 (mod Ξ»(n))
Sick! Now we have everything needed for our public and private keys.
Reminder:
- Public Key: (n,e)
- Private Key: (n,d)
- p, q, Ξ»(n) are kept secret since these values are used to calculate the secret key.
This keypair is now ready for use.
Press Enter to continue...
________________________________________________________________________________________________
One of the main security notions surrounding RSA is simply the fact that factoring n is a **hard** problem.
It straight up takes way too much computational power to factor a large number such as n.
Although using numbers this large makes us secure against today's computational power, RSA is considered slow
in the world of Cryptography because of the number crunching it takes for doing modular exponentiation compared
to that of block ciphers and other encryption schemes that have quicker security mechanisms. Funnily enough,
assymetric cryptography is mainly used to send symmetric keys instead of sharing data.
Press Enter to continue...
________________________________________________________________________________________________
Now, hopefully you understand the basic cogs of the RSA machine and some of the math behind it. Unfortunately,
RSA isn't always implemented correctly, opening the possibility of attacks. As you work your way through this quiz,
I recommend using some prett nice Python crypto/number libraries: gmpy/gmpy2, pycryptodome, binascii, and pwntools.
The three parts to the quiz each have a primitive attack on an improper implementation of RSA. Solve all 3 to get
the flag. Π£Π΄Π°ΡΠΈ!
Press Enter to exit back to main menu
________________________________________________________________________________________________
/------------------------\
| Baby RSA MENU: |
| (0) Teach me some RSA! |
| (1) Skip to quiz |
| (2) Quit |
\------------------------/
Choice: 1
___________________________________________________________________________________
I see you are ready to take my quiz! This quiz is comprised of three parts with
each part giving you a poor implementation of RSA. If you are unfamiliar with any
of these values given, it might be worthwhile to check out option 0 in the main
menu.
---------
| Part 1: |
---------
n = 205740152270759
e = 65537
ct = 34242279562215
What is the plaintext (in integer form)?What did we do!
Last updated
