Day 53: RSA Encryption Scheme

The past two days were tough, but today I am finally ready to complete the algorithm for RSA encryption scheme.

disclaimer: do not consider my code to be secure; do not consider any cryptography coming from non-experts to be secure; you should never implement any kind of cryptography on your own nor should you interfere with your security in any way; this series is just for fun and as such should be taken

I have large prime numbers and know how to generate RSA keys and how to use them.

One more tool is needed, though, a strong pseudo-random generator. I will use SHA-512. It is a secure hash function, and to be secure it has to comply some special demands. Among others, it has to be a secure PRG.

My recipe is inspired by RSA OAEP, which is used in practice.

Assuming I have two 1024-bit primes, 2048-bit modulus, random generator and SHA-512, I can transfer up to 192-byte message.

Here are the steps:

  1. IV: generate 64-byte block of random values
  2. H1, H2, H3: apply repetitively SHA-512 to produce 64-byte blocks of uniform random values
  3. X192: XOR plaintext message with concatenated block H1|H2|H3
  4. X64: use SHA-512 on block X192 to produce another 64-byte block of uniform random values and XOR with IV
  5. encrypt: RSA(X192|X64, public_key)

The key idea is that randomization of raw message makes encryption non-deterministic and chosen-ciphertext secure. The final 256-byte message X192|X64 is fully random with uniform distribution. It can be proved, but I promised no math today.

As a showcase there are two samples at the end of this article. In both cases plaintext 0 is encrypted and each time results in a different ciphertext.

Is my implementation really secure? I’m not sure since I can’t prove that. But I am sure I would have never use it in real application :-)


def bxor(x, y): 
return bytes(i ^ j for i, j in zip(x, y))

def rsa_encrypt(plaintext, public_key):
# iv[64] -> h1[64] -> h2[64] -> h3[64]
iv = urandom(64)
h1 = sha512(iv).digest()
h2 = sha512(h1).digest()
h3 = sha512(h2).digest()

# x[192] := pt[192] ^ (h1|h2|h3)[192]
pt = int.to_bytes(plaintext, 192, 'big')
x192 = bxor(pt, h1 + h2 + h3)

# x[64] := iv[64] ^ x[192->64]
h4 = sha512(x192).digest()
x64 = bxor(iv, h4)
    # x[256] := x[192]|x[64]
x256 = int.from_bytes(x192 + x64, 'big')
    # rsa
return pow(x256, *public_key)

def rsa_decrypt(ciphertext, secret_key):
# rsa
x256 = pow(ciphertext, *secret_key)

# x[192]|x[64] := x[256]
x256 = int.to_bytes(x256, 256, 'big')
x192, x64 = x256[:192], x256[192:]

# iv[64] := x[64] ^ x[192->64]
h4 = sha512(x192).digest()
iv = bxor(x64, h4)
    # iv[64] -> h1[64] -> h2[64] -> h3[64]
h1 = sha512(iv).digest()
h2 = sha512(h1).digest()
h3 = sha512(h2).digest()

# pt[192] := x[192] ^ (h1|h2|h3)[192]
pt = bxor(x192, h1 + h2 + h3)

# plaintext
return int.from_bytes(pt, 'big')

dummy message #1

> rsa_encrypt(0, public_key)

dummy message #2

> rsa_encrypt(0, public_key)
Show your support

Clapping shows how much you appreciated Tomáš Bouda’s story.