## RSA

RSA, first described in 1977, is the most famous public-key cryptosystem. It has two main use-cases:

• Public key encryption enables a user, Alice, to distribute a public key and others can use that public key to encrypt messages to her. Alice can then use her private key to decrypt the messages.
• Digital signatures enable Alice to use her private key to "sign" a message. Anyone can use Alice's public key to verify that the signature was created with her corresponding private key, and that the message hasn't been tampered with.

Although RSA's security is based on the difficulty of factoring large composite numbers, in recent years the cryptosystem has received criticism for how easy it is to implement incorrectly. Major flaws have been found in common deployments, the most notorious of these being the ROCA vulnerability which led to Estonia suspending 760,000 national ID cards.

These challenges introduce you to the many footguns of RSA, and soon see you performing attacks which have caused millions of dollars of damage in the real world.

#### Starter

Toggle
• Modular Exponentiation
10 pts ·
All operations in RSA involve modular exponentiation.

Modular exponentiation is an operation that is used extensively in cryptography and is normally written like: $2^{10} \mod 17$

You can think of this as raising some number to a certain power ($2^{10} = 1024$), and then taking the remainder of the division by some other number ($1024 \mod 17 = 4$). In Python there's a built-in operator for performing this operation: pow(base, exponent, modulus).

In RSA, modular exponentiation, together with the problem of prime factorisation, helps us to build a "trapdoor function". This is a function that is easy to compute in one direction, but hard to do in reverse unless you have the right information. It allows us to encrypt a message, and only the person with the key can perform the inverse operation to decrypt it.

To grab the flag, find the solution to $101^{17} \mod 22663$

You must be logged in to submit your flag.

• Public Keys
15 pts · 10226 Solves
RSA encryption is modular exponentiation of a message with an exponent $e$ and a modulus $N$ which is normally a product of two primes: $N = p \cdot q$.

Together, the exponent and modulus form an RSA "public key" $(N, e)$. The most common value for $e$ is 0x10001 or $65537$.

"Encrypt" the number $12$ using the exponent $e = 65537$ and the primes $p = 17$ and $q = 23$. What number do you get as the ciphertext?

You must be logged in to submit your flag.

• Euler's Totient
20 pts · 9722 Solves
RSA relies on the difficulty of the factorisation of the modulus N. If the prime factors can be deduced, then we can calculate the Euler totient of N and thus decrypt the ciphertext.

Given $N = p \cdot q$ and two primes:

p = 857504083339712752489993810777
q = 1029224947942998075080348647219

What is Euler's totient $\phi(N)$?

You must be logged in to submit your flag.

• Private Keys
20 pts · 9100 Solves
The private key $d$ is used to decrypt ciphertexts created with the corresponding public key (it's also used to "sign" a message but we'll get to that later).

The private key is the secret piece of information, or "trapdoor", which allows us to quickly invert the encryption function. If RSA is implemented well, if you do not have the private key the fastest way to decrypt the ciphertext is to factorise the modulus which is very hard to do for large integers.

In RSA, the private key is the modular multiplicative inverse of the exponent $e$ modulo $\phi(N)$, Euler's totient of $N$.

Given the two primes:

p = 857504083339712752489993810777
q = 1029224947942998075080348647219

and the exponent $e = 65537$, what is the private key $d \equiv e^{-1} \mod \phi(N)$?

You must be logged in to submit your flag.

• RSA Decryption
20 pts · 8783 Solves
I've encrypted a secret number for your eyes only using your public key parameters:

N = 882564595536224140639625987659416029426239230804614613279163
e = 65537

Use the private key that you found for these parameters in the previous challenge to decrypt this ciphertext:

c = 77578995801157823671636298847186723593814843845525223303932

You must be logged in to submit your flag.

• RSA Signatures
25 pts · 6724 Solves
How can you ensure that the person receiving your message knows that you wrote it?

You've been asked out on a date, and you want to send a message telling them that you'd love to go, however a jealous lover isn't so happy about this.

When you send your message saying yes, your jealous lover intercepts the message and corrupts it so it now says no!

We can protect against these attacks by cryptographically signing the message.

Imagine you write a message $m$. You encrypt this message with your friend's public key: $c = m^{e_{0}} \mod N_{0}$.

To sign this message, you calculate the hash of the message: $H(m)$ and "encrypt" this with your private key: $s = H(m)^{d_{1}} \mod N_{1}$.

In real cryptosystems, it's best practice to use separate keys for encrypting and signing messages.

Your friend can decrypt the message using their private key: $m = c^{d_{0}} \mod N_{0}$. Using your public key they calculate $s = S^{e_{1}} \mod N_{1}$.

Now by computing $H(m)$ and comparing it to $s$: assert H(m) == s, they can ensure that the message you sent them, is the message that they received! As long as your private key is safe, no one else could have signed this message!

Sign the flag crypto{Immut4ble_m3ssag1ng} using your private key and the SHA256 hash function.

The output of the hash function needs to be converted into a number that can be used with RSA math. Remember the helpful bytes_to_long() function that can be imported from Crypto.Util.number.

Challenge files:
- private.key

You must be logged in to submit your flag.

#### Primes Part 1

Toggle
• Factoring
15 pts · 6946 Solves
So far we've been using the product of small primes for the modulus, but small primes aren't much good for RSA as they can be factorised using modern methods.

What is a "small prime"? There was an RSA Factoring Challenge with cash prizes given to teams who could factorise RSA moduli. This gave insight to the public into how long various key sizes would remain safe. Computers get faster, algorithms get better, so in cryptography it's always prudent to err on the side of caution.

These days, using primes that are at least 1024 bits long is recommended—multiplying two such 1024 primes gives you a modulus that is 2048 bits large. RSA with a 2048-bit modulus is called RSA-2048.

Some say that to really remain future-proof you should use RSA-4096 or even RSA-8192. However, there is a tradeoff here; it takes longer to generate large prime numbers, plus modular exponentiations are predictably slower with a large modulus.

Factorise the 150-bit number 510143758735509025530880200653196460532653147 into its two constituent primes. Give the smaller one as your answer.

Resources:
- How big an RSA key is considered secure today?
- primefac-fork

You must be logged in to submit your flag.

• Inferius Prime
30 pts · 5072 Solves
Here is my super-strong RSA implementation, because it's 1600 bits strong it should be unbreakable... at least I think so!

Challenge files:
- inferius.py
- output.txt

You must be logged in to submit your flag.

• Monoprime
30 pts · 6197 Solves
Why is everyone so obsessed with multiplying two primes for RSA. Why not just use one?

Challenge files:
- output.txt

Resources:
- Why do we need in RSA the modulus to be product of 2 primes?

You must be logged in to submit your flag.

• Square Eyes
35 pts · 4577 Solves
It was taking forever to get a 2048 bit prime, so I just generated one and used it twice.

If you're stuck, look again at the formula for Euler's totient.

Challenge files:
- output.txt

You must be logged in to submit your flag.

• Manyprime
40 pts · 5483 Solves
Using one prime factor was definitely a bad idea so I'll try using over 30 instead.

If it's taking forever to factorise, read up on factorisation algorithms and make sure you're using one that's optimised for this scenario.

Challenge files:
- output.txt

Resources:
- The Elliptic Curve Factorization Method

You must be logged in to submit your flag.

Toggle

#### Primes Part 2

Toggle
• Infinite Descent
50 pts · 2498 Solves
Finding large primes is slow, so I've devised an optimisation.

Challenge files:
- descent.py
- output.txt

You must be logged in to submit your flag.

• Marin's Secrets
50 pts · 2450 Solves
I've found a super fast way to generate primes from my secret list.

Challenge files:
- marin.py
- output.txt

You must be logged in to submit your flag.

• Fast Primes
75 pts · 1619 Solves
I need to produce millions of RSA keys quickly and the standard way just doesn't cut it. Here's yet another fast way to generate primes which has actually resisted years of review.

Challenge files:
- fast_primes.py
- key.pem
- ciphertext.txt

You must be logged in to submit your flag.

• Ron was Wrong, Whit is Right
90 pts · 1505 Solves
Here's a bunch of RSA public keys I gathered from people on the net together with messages that they sent.

As excerpt.py shows, everyone was using PKCS#1 OAEP to encrypt their own messages. It shouldn't be possible to decrypt them, but perhaps there are issues with some of the keys?

Challenge files:
- excerpt.py
- keys_and_messages.zip

Resources:
- The recent difficulties with RSA

You must be logged in to submit your flag.

• RSA Backdoor Viability
175 pts · 1145 Solves
It seems like my method to generate fast primes was not completely secure. I came up with a new approach to improve security, including a factorization backdoor in case I ever lose my private key. You'll definitely need some complex techniques to break this!

You may need to tweak the recursion limit (sys.setrecursionlimit(n) in Python) in your programming language to get your solution working.

Challenge files:
- complex_primes.py
- output.txt

Challenge contributed by joachim

You must be logged in to submit your flag.

Toggle
100 pts · 940 Solves
Been cooking up my own padding scheme, now my encrypted flag is different everytime!

Connect at socket.cryptohack.org 13386

Challenge files:
- 13386.py

You must be logged in to submit your flag.

• Null or Never
100 pts · 1044 Solves
Can custom padding save one from some of the mistakes we already covered?

Challenge files:
- output.txt

You must be logged in to submit your flag.

#### Signatures Part 1

Toggle
• Signing Server
60 pts · 1576 Solves
My boss has so many emails he's set up a server to just sign everything automatically. He also stores encrypted messages to himself for easy access. I wonder what he's been saying.

Connect at socket.cryptohack.org 13374

Challenge files:
- 13374.py

You must be logged in to submit your flag.

• Let's Decrypt
80 pts · 1015 Solves
If you can prove you own CryptoHack.org, then you get access to one of our secrets.

Connect at socket.cryptohack.org 13391

Challenge files:
- 13391.py

You must be logged in to submit your flag.

• Blinding Light
120 pts · 1107 Solves
Here's my token signing and verification server. I'm not sure it's doing signing properly, but I've implemented some safeguards to ensure it won't hand out admin tokens to just anyone.

Connect at socket.cryptohack.org 13376

Challenge files:
- 13376.py

You must be logged in to submit your flag.

#### Signatures Part 2

Toggle
• Vote for Pedro
150 pts · 810 Solves
If you want my flag, you better vote for Pedro! Can you sign your vote to the server as Alice?

Connect at socket.cryptohack.org 13375

Challenge files:
- 13375.py
- alice.key

You must be logged in to submit your flag.

• Let's Decrypt Again
175 pts · 480 Solves
Let's Decrypt was too easy, let's do it again!

Connect at socket.cryptohack.org 13394

Challenge files:
- 13394.py

Challenge contributed by Robin_Jadoul and Thunderlord

You must be logged in to submit your flag.

### Level Up

You are now level Current level