Page cover image

☠️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