Elliptic curves in FOSS
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Subtitle |
| |
| Title of Series | ||
| Number of Parts | 542 | |
| Author | ||
| License | CC Attribution 2.0 Belgium: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/61957 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
FOSDEM 2023380 / 542
2
5
10
14
15
16
22
24
27
29
31
36
43
48
56
63
74
78
83
87
89
95
96
99
104
106
107
117
119
121
122
125
126
128
130
132
134
135
136
141
143
146
148
152
155
157
159
161
165
166
168
170
173
176
180
181
185
191
194
196
197
198
199
206
207
209
210
211
212
216
219
220
227
228
229
231
232
233
236
250
252
256
258
260
263
264
267
271
273
275
276
278
282
286
292
293
298
299
300
302
312
316
321
322
324
339
341
342
343
344
351
352
354
355
356
357
359
369
370
372
373
376
378
379
380
382
383
387
390
394
395
401
405
406
410
411
413
415
416
421
426
430
437
438
440
441
443
444
445
446
448
449
450
451
458
464
468
472
475
476
479
481
493
494
498
499
502
509
513
516
517
520
522
524
525
531
534
535
537
538
541
00:00
CollaborationismCurveEllipsePoint (geometry)Congruence subgroupOpen setExecution unitTorsion (mechanics)Local GroupSubgroupCryptographyPositional notationInfinityDiskreter LogarithmusKörper <Algebra>Koblitz, NealIndependence (probability theory)Form (programming)Reduction of orderNormal (geometry)CryptanalysisPrime idealVorwärtsfehlerkorrekturStandard deviationComputer fontPresentation of a groupKernel (computing)RSA (algorithm)Address spaceRevision controlEuclidean vectorEquivalence relationPublic-key cryptographyPrimality testVector potentialBuildingImplementationMilitary operationEncryptionJacobi methodKörper <Algebra>EllipseImplementationElliptic curveCurveFunctional (mathematics)Multiplication signDifferent (Kate Ryan album)Address spaceVariety (linguistics)Connectivity (graph theory)SubsetPresentation of a groupTorsion (mechanics)CalculationPhysical systemElectronic signatureStandard deviationWell-formed formulaMathematicsParameter (computer programming)Level (video gaming)Point (geometry)Axiom of choiceCongruence subgroupElement (mathematics)Galois-FeldBoom (sailing)MappingRevision controlOrder (biology)SoftwareBitHash functionEvolutePublic-key cryptographyNumberCASE <Informatik>Beat (acoustics)Domain nameCryptographyPlotterCubeStatement (computer science)Real numberEuklidische GeometrieFinitismusCharacteristic polynomialComputer fontInfinityGenerating set of a groupMedical imagingFreewareIndependence (probability theory)Service (economics)Set (mathematics)Zyklische GruppeForm (programming)Point at infinityAbelsche GruppeNational Institute of Standards and TechnologyDegree (graph theory)Kernel (computing)Normal-form gameCryptanalysisPatch (Unix)Constraint (mathematics)Operator (mathematics)Open sourceEquivalence relationLatent heatSingle-precision floating-point formatParity (mathematics)Condition numberSlide ruleVideoconferencingDiagramComputer animation
09:12
CollaborationismMilitary operationEncryptionJacobi methodOpen setOperations researchTexture mappingTransformation (genetics)Group actionCurveCodierung <Programmierung>EllipseMathematicsLatent heatRandom numberFunction (mathematics)Hash functionInclusion mapFormal verificationParameter (computer programming)Streaming mediaCryptographyAxiom of choiceCryptanalysisVorwärtsfehlerkorrekturElectronic signatureElliptic curveMatching (graph theory)Streaming mediaMatrix (mathematics)1 (number)Group actionParameter (computer programming)Service (economics)CryptographyPlotterVariety (linguistics)Point (geometry)Communications protocolShape (magazine)Internet der DingeCurveOperator (mathematics)Körper <Algebra>WeightStandard deviationCategory of beingMultiplication signHash functionRandom number generationHyperelliptische KurveOpen sourceOrder (biology)Information securityDirection (geometry)VideoconferencingComplete metric spaceRecursionHomomorphismusSoftwareImplementationFreewareResultantElement (mathematics)DemosceneCycle (graph theory)Data miningLevel (video gaming)NumberTransformation (genetics)MappingConfidence intervalMathematicsExtension (kinesiology)Set (mathematics)Computer animation
18:16
VorwärtsfehlerkorrekturComputer animationProgram flowchart
Transcript: English(auto-generated)
00:08
Hello and welcome to the Forstens Security Dev Room, this is a talk about elliptic curbs in free and open source software. The room's audio and video wasn't recorded properly so I will record my voice on top
00:20
of these slides trying to fix it. My name is Sergi Blanc-Tournay and I do this activity as a member of Collabra. Here is the overline of the presentation and the first thing that we will do is an overview of elliptic curbs themselves. The first question to talk about is the what, so what's an elliptic curve, and this will
00:41
follow everything else in this talk. An elliptic curve is a function and a very finite field is understood as a congruency with a odd number and it must satisfy the condition to not have singular points, mathematically we know that because it has a non-zero discriminant. This is how an elliptic curve plot in the real plane looks like, perhaps even it's an
01:04
image that looks familiar, but if we plot it over in a small finite field this is how it looks like, so you will see that the real numbers extend to the infinity but this is not happening over a finite field. So to later do the maths we need to union this set of points to the point of
01:25
infinity to set something that is complete. Once we have a set of points of an elliptic curve with this point at infinity we can define a cyclic subgroup that is where the crypto will happen. An important thing to mention is the notation, if you see here is different than the crypto
01:44
over finite fields that we may use to, but the difference is that here we are using additive notation instead of the multiplicative one, perhaps you already seen before. The same way in elliptic curves we have a generator of the cyclic group that we provide as the strength required to do crypto, the order or the size of the cyclic group must
02:06
be big enough and there is a relationship between the number of points of this elliptic curve and the order of this cyclic subgroup, this is called the decofactor and this is a very important parameter that would affect almost everything later on. Until here the hard math, I don't need for this talk to enter further to explain the
02:26
torsion points or even isogeneous. The first proposal to use elliptic curves and cryptology comes from an independent proposal from Koblitz and Miller. The functions commonly used here are the Weierstrass reduced form and they are different
02:41
when it is defined over a primary field or when it is defined over a field extension, but they are subsets of the parameterization of the Weierstrass normal form. A common variety of the elliptic curves are the Montgomery curves that follows this formula and these curves are used together with the map to the Edward curves and you
03:04
will often hear about if they are twisted or not. There is a recent proposal to use what so called double odd curves that takes benefit from another map to Jacobi quartic curves and these last two mappings are very important for the current evolution of the elliptic cryptography.
03:23
Next question is why? Why elliptic curves are better to set up cryptography than the common generalized use of finite fields? The first benefit is the size of this prime p that is required to be much larger in finite fields, 2000 up to 4000 beats nowadays, when in elliptic curves you can have the
03:43
equivalent sizes between around 250 and 500 beats. This statement has a but that has to be remarked here. The size of the finite field over which the elliptic cube is defined is smaller, so the operations are over the smaller numbers, but the operations between the points required
04:05
much more operations over the underlying finite field, so don't expect them to be much different in time. Another difference is that elliptic curves can be defined over more fields than the finite ones, as they are the characteristic to file extensions, but the most important
04:22
advantage that elliptic curves gives us is the possibility to use different elliptic curves over the same finite field. This is a huge impact over the cryptanalysis, because one cannot use efficiently the cryptanalysis made over one curve when you are using a different one, and the main beneficiary of
04:43
this feature is the embedded systems that doesn't need to change the size of the calculations by resetting the curve. Next element in the outline is the standards defined for the elliptic curves cryptography. The first standard that I know about were from the 2000s, in the text of the NIST
05:02
or the ANSI, standardized specifics on single elliptic curves for different sizes. It is important to mention that x962 specifically mentioned that shared elliptic curve means to share the cryptanalysis. With them, more elliptic curves come to the scene, and newer standards that specify
05:23
different curves but over the same variety. In the two decades that passes, many more standards come to the scene, but fundamentally fixing single elliptic curves for a specific finite field size. I couldn't do this presentation without remembering xkcd.
05:42
Let's go talk on the main thing on this presentation, that is, the implementations. Here is a non-exhaustive table of different tools and packages that I know that they have elliptic curves implemented. First implementation is the OpenSSL, because if I'm not wrong, it was the first implementation
06:04
of elliptic curves in free software. They made the implementation in both underlying fields, finite fields and characteristic tool. The next one is the libgcrypt that promotes a patch that I've made in the baccalauret degree for the GNU PG 1.4.
06:23
And then many other implements the elliptic curves like GNU TLS and later on the kernel itself. After that the boom happens, and many more implements this cryptographic setup. And with the proposal of the new elliptic curves of using edu-verse curves, almost
06:43
all of them have also included the math to work with this elliptic curve. One place where the elliptic curves are present for the general public is the Tor network. I haven't listed them before, because from my point of view, it's a very special case. The onion addresses in the version 2 of the specs use a truncated hash of an RSI key
07:05
embedded within the 16 characters of the onion address. With this version 3, there is no truncation, and it contains completely the public key. And this public key is a point of an elliptic curve using the standard curve. With this concatenation, we have these 56 characters currently used in the onion addresses.
07:27
So much more tricks has been necessary because the torsion component of this curve that is related with the fact that it has a cofactor 8. There could be multiple equivalent addresses pointing to the same service.
07:41
So continue with those new elliptic curves and more standards that are coming. First of all, this Edward curve that is a Montgomery curve with a variational map with two other curves, one is twisted and the other is non-twisted. And as explained in the standard, there are some constraints to have better choices
08:00
in the range, so those are the parameters proposed. And this standard gives us one specific curve for the 255 bits, and a second curve with a bigger strength of 448 bits. Both using this map to other curves to move the domain of some operations to the curve
08:24
that can do it better and faster to later go back to the elliptic one. Following this idea of plotting elliptic curves, you can see here the plot over the real numbers, as well as the same plot, the same curve, but over a small finite field.
08:41
The last curve I plotted here is the pair of twisted and untwisted curves. What makes those curves special is that they have been designed to avoid common issues we learn with implementations of elliptic curves. So they are designed to be immune to timing attacks.
09:00
There is a relatively new proposal to use another Montgomery curve. This time the prime p to define the finite field is different depending if the purpose is to encrypt or if the purpose is for digital signatures. And in this case, we have a much better cofactor than these two. In this proposal, they are taking benefit also from the mapping to the Edward curves.
09:22
In this case, a plot over the real showed a very different shape with coordinates origin in the most left-hand side of the curve. By the way, this is something you don't see visually in the plot over a small finite field, but it's an interesting property of this variety.
09:40
Even more recently, it has been proposed to upgrade this with the use of another mapping to a Jacobic hortic curve that improve the coordinates transformation and the operations in the map much better. It makes operation faster and signature shorter. Then let's go to see if we can choose our elliptic curve.
10:00
There is a draft talking about the ristretto and the calf and later we will talk about zoo. The calf is a technique mainly thought to construct elliptic curves with a small cofactor, but bigger than one. And then comes ristrettos, an extension of this technique for the variety of curves where the Edward curves in 255 bit are.
10:24
This proposal takes advantage from both mappings, so this is proposing to use the variety of elliptic curves taking benefit from the advantages of those two maps, Edwards and Jacobic hortic. And this is not to specify a single curve. This is a very important step. This is to specify and standardize the maths and operations to work with
10:44
a complete variety of elliptic curves. Perhaps some smart cryptographers have started to move in the direction to give us the possibility to not share elliptic curves between each other. This reminds me a paper from 2015 from Leinster and Velowski that talks about the zoo.
11:02
A zoo of actors in this proposal to have a public and auditable generator of elliptic curves. So let's go into the details which are the members of this zoo. First of all is an important sloth and this is a hash algorithm that requires time. It is slow by design.
11:21
There is a unicorn that comes to the scene and this is a special random number generator. It is not the usual random number generator because it is made to allow all of us to influence the result. We can influence and verify that our contribution is included. What makes it good is that a counter contribution is hard,
11:43
so it is hard for another participant to prepare a contribution and counteract all at once. The next element in this zoo is the T-R-X. I am not sure if this is a real way to pronounce this T-R-X. This member of the zoo uses the unicorn to stream a trusty random generator of elliptic curves parameters
12:00
fitting the cryptography requirements. With this, we all can influence the generator of a fresh elliptic curve and verify our contribution. But no one can counteract our contribution effectively. The result cannot be known beforehand and cannot be manipulated to provide previously known results.
12:20
This prevents prior kryptanalyses and also provides confidence about how the parameters were selected. Linked to the ANSI X962 about the fact that we are sharing elliptic curves, we are sharing also kryptanalyses together with the fact that it is expensive to generate an elliptic curve cryptographically good
12:41
and also together with the movement to standardize a variety of elliptic curves but not a single one, we can set as a corollary that by saying that there is a movement to fix this small set of elliptic curves that we've been struggling during two decades. It seems that we are working a very nice path in elliptic curves
13:03
and Free Software is the only actor that can provide this trusty elliptic curves generator. So that's all and now the video and audio from the room gets back. So that's all from my side in this little review on the elliptic curves itself and thinking in the implementations in Free Software.
13:41
Hi, you were talking about standardization of curves but with a lot of new cryptography techniques like zero-knowledge, homomorphic encryption, MPC, VDFs and then even when you start talking about recursion
14:00
and curve cycles and pairing friendly curves, each time it seems people try to standardize curves and then discover like there's some new property like maybe unknown order groups or hyperlyptic. I think the movement of this restricted one, the curve, goes in the direction instead of standardize an elliptic curve itself,
14:26
it is standardizing a variety of elliptic curves. Then you have the operations and the match to work with any elliptic curves in this variety. So this will bring us the possibility to have this like another service that is providing random elliptic curves on the net
14:43
and you can pick one from there and forget about the thing that we are sharing the same elliptic curves of this. The way that all the current standards that exist are fixing an elliptic curve, one or another, but fixing in a specific way.
15:00
I answered it because you say about homomorphic but homomorphic is huge, it's a very interesting field but it's a huge field. Okay, I can see another question.
15:20
In many protocols and also in IoT devices, you are bottlenecked by speed and also by signature size. You said that with the jacobiquatic curve you can go faster and also smaller. How much faster and how much smaller? I have in the paper of the jacobiquatic people, the speed is explained, I don't have the numbers on mine now.
15:48
I have the numbers on mine about the size because the sizes in signatures in elliptic curves are 64 bytes and the schema they propose for the jacobiquatic is 84 bytes, so it's like a third smaller.
16:07
But it's still bigger than BLS signatures who are about 32 to 48 because you only need a single point on the curve. In the signature, you are not putting only the point. There are three, if I remember correctly.
16:24
BLS signatures, it's only one point. Which signature? BLS from Dan Bonnet. But it's shorter than 48 bytes? It depends on the base curve you use but it's only, so if you
16:42
use, well, 32-byte signatures are not deemed secure enough because you have pairing issues but 48 bytes provides 128 bytes of security. What I know is that in the Edward Kirp's variety, the signature is 64 bytes.
17:09
Okay, are there any questions? Have you looked at Genes II curves? Because I saw that they outperform Genes II.
17:27
They outperform Genes I. I saw DJB was really into them. You are? Hyper-elliptic curves? Yeah, the Picard group. This is a very nice subject also. I think banks are the ones that are putting more money in hyper-elliptic curves.
17:44
They are not using points, they are using a matrix that is Jacobian of the point. By now, I only heard about banks putting money there. I haven't seen an implementation in open source.
18:06
Any other? No? Thank you.