## RSA Starter 1

### Description

All operations in RSA involve modular exponentiation.

Modular exponentiation is an operation that is used extensively in cryptography and is normally written like: 2¹⁰ mod 17

You can think of this as raising some number to a certain power (2¹⁰ = 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.

Find the solution to 101¹⁷ mod 22663

## RSA Starter 2

### Description

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 * 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?

## RSA Starter 3

### Description

RSA relies on the difficulty of the factorisation of the modulus N. If the primes can be found then we can calculate the Euler totient of N and thus decrypt the ciphertext.

Given N = p*q and two primes:

What is the totient of N?

## RSA Starter 4

### Description

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 first factorise the modulus.

In RSA the private key is the modular multiplicative inverse of the exponent e modulo the totient of N.

Given the two primes:

and the exponent:

What is the private key d?

## RSA Starter 5

### Description

I’ve encrypted a secret number for your eyes only using your public key parameters:

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

## RSA Starter 6

### Description

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 signing the message.

Imagine you write a message M. You encrypt this message with your friend’s public key: C = Mᵉ⁰ mod N₀.

To sign this message, you calculate the hash of the message: H(M) and “encrypt” this with your private key: S = H(M)ᵈ¹ mod N₁.

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ᵈ⁰ mod N₀. Using your public key they calculate s = Sᵉ¹ mod N₁.

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!

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

### Analyze

Alice 向 Bob 发送消息：

1. 用 Bob 的公钥加密得到 C

2. 签名

签名步骤

1. 求消息的哈希值 H
2. 用 Alice 的私钥“加密”哈希值得到 S

Bob 接收 Alice 的消息：

1. 用 Bob 的私钥解密得到 m
2. 用 Alice 的公钥计算“解密”得到 s
3. 计算消息的哈希值 H
4. 比较 s 和 H，二者相等就能确定消息是真实的