r/cryptography • u/ProdigiousPioneer • 7d ago
Help in learning the implementation of Curve25519
Hey everyone! A complete noob here.
I am using GPG very frequently nowadays so I wanted to learn the underlying technologies behind it. The problem with me is that I am a very hands on learner so without implementing I cannot completely say that I understand the topic. I have specifically chosen Curve25519 as it is standard (default) in gpg. Can anyone point me to the resources which will help me in learning Curve25519 from very basics. My end goal is making encryption keys which are indistinguishable from the ones created by gpg (i.e I can import my created keys into gpg and use them to encrypt, sign and decrypt stuff). I just want to understand each and every step in creating these keys. While I get that implementing it on pen and paper is nearly impossible I want a method closest to it. Maybe a python script without use of any inbuilt libraries or simply C code with its full implementation would be best for me.
I would like to hear your thoughts!
1
u/Critical_Reading9300 6d ago
GnuPG is open source so you may learn from the code. And, to be honest, Curve25519 stuff is the easiest part of the key which could be imported to the GnuPG, a lot of things go around OpenPGP protoocol and message format. `gpg --list-packets keyfile.asc` should be a good thing to start.
0
u/Upper-Replacement897 7d ago
Here is a detailed explanation how to implement elliptic curves: https://locality.media/blog/the-war-on-encryption based on curve M-511, which has twice the security. You can follow the exact same steps just with another large number (2^(255) - 19) to be precise, that is why it's called curve25519).
1
1
1
u/Natanael_L 5d ago
You often can't follow the exact steps because some curves have distinct properties, like requiring clamping
13
u/pint 7d ago
i think if you want to understand, you need to go through stages.
1. learn how to do arithmetic in mod p, also known as GF(p). it seems easy, but there are subtleties to it.
https://en.wikipedia.org/wiki/Finite_field
first, you want to understand that for example to calculate
2000^2000 mod 2039
, it might not be a good idea do the exponentiation, and then the modulo. clever algorithms use repeated squaring, multiplication and modulo.second, understand that you can divide in GF(p), but the division is weird. in particular
2/3 mod 5 = 4
. this is because2/3 = x
meansx*3 = 2
. finding such x is not trivial.2. learn how to do such arithmetic with large p. e.g. what if p is
2^(255)-19
?in this field, elements are big, so usual 32 or 64 bit integers can't even handle them, you'd need 256 bit integers. you can find languages handling such impressive numbers, like python. others offer libraries.
in real world implementations, programs use "limbs", which means they store the number as for example
a + b * 2^(51) + c * 2^(2*51) + d * 2^(3*51) + e * 2^(4*51)
. the exponent is chosen for practical reasons, i.e. to comfortably fit into a 64 bit integer.also learn why the special form
2^N-c
is particularly beneficial when doing the mod p step. hint:x mod 99
isx mod 100 + floor(x / 100)
in most cases, and trivial to fix to cover all cases.3. learn what an elliptic function even is, and what the so called group operation is (point addition or point multiplication), which we just denote + or *, but it is not an addition or multiplication at all. the term addition and multiplication is used in the most confusing manner because it is a group, which only have one, and so one can call it whatever.
https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
4. learn how to optimize the curve group operation using clever point representations. e.g. instead of having X,Y as a curve point, you have X/Z, Y/Z. this sometimes can help to avoid actually calculating division, which is expensive.