3 ms·

I am always interested in knowing how cryptographers come up with these big big big big numbers? https://github.com/mimoo/Diffie-Hellman_Backdoor/blob/master/a

by yeukhon 11y ago

I am always interested in knowing how cryptographers come up with these big big big big numbers? https://github.com/mimoo/Diffie-Hellman_Backdoor/blob/master/attack/1024_backdoored_params https://github.com/mimoo/Diffie-Hellman_Backdoor/blob/master... They appear to be mysterious, magic numbers in every single crypto implementation. And many are written in byte form. I mean how can people comprehend them?

deleted 11y ago
[deleted]
tptacek 11y ago
People generate large primes using programs designed to do that, and maybe generators/primitive roots for those primes using a CAS like Sage or Octave/Matlab. The same goes for ECC crypto, with a lot of extra testing/filtering to find "nice" constants. A lot of the other giant numbers you see in cryptosystems are random numbers derived from other constants. Sometimes there are things to learn by studying the numbers themselves. For instance, the prime field in Curve25519 is a special prime with (bit-level) characteristics that make it especially nice to do math on with general-purpose computers. Other times, the numbers are, for instance, just giant random primes, and aren't themselves very interesting.
- yeukhon 11y ago
  I see. Thank you, tptacek. > People generate large primes using programs designed to do that Do you mind to name one such program?
  - tptacek 11y ago
    Well, anything that does RSA, right? An easy way to do this yourself is to jump into a Ruby IRB and do "OpenSSL::BN.generate_prime(512).to_s".
    - dunham 11y ago
      If I remember right, this generates a number that is probably prime. :)
      - Filligree 11y ago
        For values of "probably" that are effectively "certainly", yes.
y04nn 11y ago
Wikipedia gives some information. https://en.wikipedia.org/wiki/Primality_test https://en.wikipedia.org/wiki/Primality_test https://en.wikipedia.org/wiki/Fermat%27s_little_theorem#Generalizations https://en.wikipedia.org/wiki/Fermat%27s_little_theorem#Gene...

by yeukhon 11y ago

deleted 11y ago

[deleted]

tptacek 11y ago

People generate large primes using programs designed to do that, and maybe generators/primitive roots for those primes using a CAS like Sage or Octave/Matlab. The same goes for ECC crypto, with a lot of extra testing/filtering to find "nice" constants. A lot of the other giant numbers you see in cryptosystems are random numbers derived from other constants. Sometimes there are things to learn by studying the numbers themselves. For instance, the prime field in Curve25519 is a special prime with (bit-level) characteristics that make it especially nice to do math on with general-purpose computers. Other times, the numbers are, for instance, just giant random primes, and aren't themselves very interesting.

yeukhon 11y ago
I see. Thank you, tptacek. > People generate large primes using programs designed to do that Do you mind to name one such program?
- tptacek 11y ago
  Well, anything that does RSA, right? An easy way to do this yourself is to jump into a Ruby IRB and do "OpenSSL::BN.generate_prime(512).to_s".
  - dunham 11y ago
    If I remember right, this generates a number that is probably prime. :)
    - Filligree 11y ago
      For values of "probably" that are effectively "certainly", yes.

y04nn 11y ago

Wikipedia gives some information. https://en.wikipedia.org/wiki/Primality_test https://en.wikipedia.org/wiki/Primality_test https://en.wikipedia.org/wiki/Fermat%27s_little_theorem#Generalizations https://en.wikipedia.org/wiki/Fermat%27s_little_theorem#Gene...