Preferences

I wonder when quantum computers will be able to target post-quantum RSA [1]. Normal RSA operations (key generation, encryption, decryption) have an asymptotic advantage over Shor's algorithm, so it is not unreasonable to just use large enough keys. The advantage is similar to Merkle's puzzles [2], with the added bonus that the attacker also needs to run their attack on a quantum computer.

A while ago I generated a gigabit RSA public key. It is available at [3]. From what I remember, the format is: 4-byte little-endian key size in bytes, then little-endian key, then little-endian inverse of key mod 256**bytes. The public exponent is 3.

[1] https://eprint.iacr.org/2017/351.pdf

[2] https://dl.acm.org/doi/pdf/10.1145/359460.359473

[3] https://hristo.venev.name/pqrsa.pub


Post-Quantum RSA is clearly a joke from djb, to have a solid reply when people ask "can't we just use bigger keys"?. It has a 1-terabyte RSA key taking 100 hours to perform a single encryption. And by design it should be beyond the reach of quantum computers.

This item has no comments currently.

Keyboard Shortcuts

Story Lists

j
Next story
k
Previous story
Shift+j
Last story
Shift+k
First story
o Enter
Go to story URL
c
Go to comments
u
Go to author

Navigation

Shift+t
Go to top stories
Shift+n
Go to new stories
Shift+b
Go to best stories
Shift+a
Go to Ask HN
Shift+s
Go to Show HN

Miscellaneous

?
Show this modal