RSA
Origin
RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission. It is also one of the oldest.
Kata
In this kata we will encrypt and decrypt a message with RSA algorythm.
Build keys
- Find 2 primes numbers
pandqsuch that(2^24 + 1) < p × q < 2^32 - Compute
N = p × q - Compute
n = (p − 1) × (q − 1) - Choose
ca coprime number withnsuch that1 < c < n
(N, c) is the public key
- Determine
dasd ≡ c^−1 (mod n)that is,dis the modular multiplicative inverse ofc modulo ni.e.c*d mod n == 1.dcan be computed efficiently by using the Extended Euclidean algorithm.
(N, d) is the private key
Encrypt the message
Make a function they:
- take a message in input
- slice the message in peaces of exactly 3 bytes
- for each peaces as integer
acomputea^c mod N, you will obtain a 4 bytes integer - the concatenation of each of this numbers is the encrypted message
Decrypt the message
Make a function they:
- take an encrypted message in input
- slice the message in peaces of exactly 4 bytes
- for each peaces as integer
acomputea^d mod N, you will obtain a 3 bytes integer - the concatenation of each of this numbers is the original message
Transmit the message
For transmition using mail or other messaging tools, we must have a function they encode the encrypted message in a readable message.
Make a function they take an encrypted message in input and they output a string with only readable chars like base64 encode. Do the revert function.
Sample
- p = 51581, q = 60101
- N = 3100069681
- n = 3099958000
- c = 66797
Public key : (3100069681, 66797)
- d = 1336940133
Private key : (3100069681, 1336940133)
- Message = “Hello world!”:
0x48 0x65 0x6c 0x6c 0x6f 0x20 0x77 0x6f 0x72 0x6c 0x64 0x21 - Sliced hexadecimal:
0x48656c 0x6c6f20 0x776f72 0x6c6421 - Sliced decimal:
4744556 7106336 7827314 7103521 - Encoded message decimal:
352431401 2267192425 538638606 1131048795 - Encoded message hexadecimal:
0x1501AD29 0x87229C69 0x201AF90E 0x436A6F5B - Encoded message in base64:
FQGtKYcinGkgGvkOQ2pvWw==