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 :-)

https://github.com/coells/100days

https://notebooks.azure.com/coells/libraries/100days

algorithm

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)
35609200248139503540129603260218517496221602940067324536445751681418031331569683909682522144791083116520365950194554330147009620876344366043824162377730625474004933722838157267370464387904585338282267977104336897808403592144730304071293829094329291461756415197148068903770572154086003650217368214470127538268702947320942492147251948436544643843996896765818205343086885898610393594066974056187554075679860228489634563320493305720906554026980937833889845562994371088993955453096951811881420856576647713183694748889283362316168401328071353582815897238159071950132507167207277683912783375266771602195052789329397346575311

dummy message #2

> rsa_encrypt(0, public_key)
18898018323574713207169739737368815156509317181719456678534131142083168607240756826066625676303031925008784501151195621083343167764963532004739343469290043140833201803506277009871923901165125785709501484703971886962068991400964773473173380379440590524000422477237818289460179445852697722215674169168318309022637689373575123422495732241796429966077996938838175409908195185195551018347215719373113245998115635097143031749003652039786531118374044077205069840914997972314831445198449210058601708592249552380328009362261003877929243513821506576727122867520834050301108949396929507036108967611918803336800064832973063333128
Show your support

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