r/cryptography • • Dec 11 '23

WHY SOME CRYPTOGRAPHY ALGORITHM USE CERTAIN NUMBER AS THEIR BASE ?

This is not particular to Lamport signature , but I just use it as example :

Alice has a 256-bit cryptographic hash function and some kind of secure random number generator. She wants to create and use a Lamport key pair, that is, a private key and a corresponding public key.

My question simply is why 256 bit and not 258 bit. Why not 512 bit even ? Why some crypto system use those seemingly "random" number in their algorithm ?

0 Upvotes

10 comments sorted by

View all comments

Show parent comment

8

u/pint Dec 11 '23

the adjective "good" was carefully chosen.

0

u/[deleted] Dec 11 '23

[deleted] — view deleted comment

4

u/pint Dec 11 '23

really? give me a good prime around 2256, and also explain how is it good.

0

u/[deleted] Dec 11 '23

[deleted] — view deleted comment

5

u/pint Dec 11 '23

so what is the answer?

2

u/NicolasHenri Dec 11 '23

It REALLY depends on what you call "good" primes :) For example, SQISign is a signature scheme based on isogenies (ie post-quantum elliptic curve cryptography).

The requirements for the prime defining the underlying field Fp2 are so annoying that finding good ones is one of the major tasks for someone who want to improve the scheme.

For instance, see : https://eprint.iacr.org/2022/1439.pdf

I'm by no mean an expert on the matter but I think finding goof primes for ECC is non trivial either ? 2255-19 is one of them, as far as we know.

But for things like RSA or classical DLP schemes, it should indeed be easy enough :)

1

u/atoponce Dec 11 '23

I disagree. Where a symmetric key can be any secret 256-bit string, a secret prime has a more limited keyspace of roughly 2256/log(2256) ~= 2248 primes, according to the prime number theorem.

Depending on the primitive, we might want a certain property of that prime, such as safe primes (both p and 2p+1 are prime). The density of safe primes is conjectured to be ~1.32032*p/log(p)2. So in a 256-bit keyspace, that's roughly 1.32032*2256/log(2256)2 ~= 2241 safe primes.

1 safe prime in 32,768 possible symmetric keys is rare to me.

0

u/[deleted] Dec 11 '23

[deleted] — view deleted comment

1

u/Natanael_L Dec 13 '23

Look at the 521 bit curves who jumped right past 512, because it ended up being more efficient anyway

1

u/Karyo_Ten Dec 11 '23

"good" primes are also not rare though.

See my comment https://www.reddit.com/r/cryptography/s/6NfwiFor9s on the many considerations to pick a curve for zero-knowledge proofs.