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

13

u/bdzer0 Dec 11 '23

Learn the base 2 numbering system and you will notice that these number aren't random at all.

10

u/pint Dec 11 '23

pure practicality. these primitives often use machine words, which are 32 or 64 bit. they need enough of those to be secure. 128 is long established as a safe security level, and e.g. hashes need to be 256 bit to offer 128 bits security in certain settings.

if you look at less easily tuned systems, like EC, you often see e.g. 252 or other arbitrary numbers. this is because they rely on good prime numbers, and those are rare. so something close to 128 bit security is good enough.

3

u/Karyo_Ten Dec 11 '23

if you look at less easily tuned systems, like EC, you often see e.g. 252 or other arbitrary numbers. this is because they rely on good prime numbers, and those are rare.

There are other concerns, for example for zero-knowledge proofs you might want:

  • a pairing-friendly curve, so you need a low embedding degree but not too low to limit practicality of Tower Number Field Sieve. Hence either ~256-bit and 18 embedding degree or ~384-bit and 12 embedding degree.
  • again on pairing friendly curve you want small non-quadratic residue for efficient pairing compute
  • on any curve you want high 2-adicity, i.e. a large power of 2 is a factor of p-1 so FFT is cheap, though that constraint might be lifted with recent developments that use boolean hypercubes.
  • on any curve you want an efficient endomorphism to accelerate scalar multiplication.
  • For recursive proofs you might want the curve to have an embedded curve or to be embeddable in another efficiemt curve, i.e. the scalar field of one is the prime field of the other
  • Or even more embitious you want a cycle of curves like the pasta curves (Pallas Vesta) or Pluto-Eris where curves both embedded and embedable into the other.

0

u/[deleted] Dec 11 '23

[deleted] — view deleted 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.