Month: August 2025

Factoring RSA100

Posted on by John

Earlier today I wrote about factoring four 255-bit numbers that I needed for a post. Just out of curiosity, I wanted to see how long it would take to factor RSA 100, the smallest of the factoring challenges posed by RSA Laboratories in 1991. This is a 100-digit (330-bit) number that is the product of two primes.

I used the CADO-NFS software. The software was developed in France, and CADO is a French acronym for Crible Algébrique: Distribution, Optimisation. NFS stands for number field sieve, the fastest algorithm for factoring numbers with over 100 digits.

RSA 100 was first factored in 1991 using a few days of compute time on an MP1 MasPar computer, a machine that cost $500,000 at the time, equivalent to around $1,250,000 today.

My effort took about 23 minutes (1376 seconds) on a System 76 Meerkat mini that I paid $600 for in 2022.

The MP1 was about the size of a refrigerator. The Meerkat is about 3″ × 3″ × 1.5″.

Pairing-unfriendly curves

Posted on by John

A couple days ago I wrote about two pair of closely related elliptic curves: Tweedledum and Tweedledee, and Pallas and Vesta.

In each pair, the order of one curve is the order of the base field of the other curve. The curves in each pair are used together in cryptography, but they don’t form a “pairing” in the technical sense of a bilinear pairing, and in fact none of the curves are “pairing-friendly” as described below.

An elliptic curve E/Fq is said to be pairing-friendly if r divides qk − 1 for some small k. Here r is the size of the largest prime-order subgroup of the curve, but since our curves have prime order p, r = p.

As for what constitutes a small value of k, something on the order of 10 would be considered small. The larger k is, the less pairing-friendly the curve is. We will show that our curves are extremely pairing-unfriendly.

Since q is not a multiple of p in our examples, there must be some power of q such at

qk = 1 mod p.

The question is whether k is large, i.e. whether the order of q mod p is large. We could try successive values of k, but that won’t get us very far. To be more clever, we use Lagrange’s theorem that says the order of an element divides the order of the group. So k must be one of the factors of p − 1. (We subtract 1 because we’re looking at the multiplicative group mod p, which removes 0.)

Finding the divisors of n − 1 requires factoring n − 1, which isn’t easy, but isn’t insurmountable either. The previous post reports the time required to do this in Python and in Mathematica for each of the following values of n.

p = 2254 + 4707489544292117082687961190295928833
q = 2254 + 4707489545178046908921067385359695873
r = 2254 + 45560315531419706090280762371685220353
s = 2254 + 45560315531506369815346746415080538113

Tweedledum has order p and its base field has order q.

k = 28948022309329048855892746252171976963322203655954433126947083963168578338816

Tweedledee has order q and its base field has order p.

k = 28948022309329048855892746252171976963322203655955319056773317069363642105856

Vesta has order r and its base field has order s.

k = 14474011154664524427946373126085988481681528240970780357977338382174983815168

Pallas has order s and its base field has order r.

k = 14474011154664524427946373126085988481681528240970823689839871374196681474048

It’s safe to say in each case k is not a small number.

 

Time to factor big integers Python and Mathematica

Posted on by John

This post will look at the time required to factor n − 1 each of the following prime numbers in Python (SymPy) and Mathematica. The next post will explain why I wanted to factor these numbers.

p = 2254 + 4707489544292117082687961190295928833
q = 2254 + 4707489545178046908921067385359695873
r = 2254 + 45560315531419706090280762371685220353
s = 2254 + 45560315531506369815346746415080538113

Here are the timing results.

    |   |   Python | Mathematica |
    |---+----------+-------------|
    | p |    0.913 |       0.616 |
    | q |    0.003 |       0.002 |
    | r |  582.107 |      14.915 |
    | s | 1065.925 |      20.763 |

This is hardly a carefully designed benchmark, but it’s enough to suggest Mathematica can be a couple orders of magnitude faster than Python.

Here are the factorizations.

p − 1 = 234 × 3 × 4322432633228119 × 129942003317277863333406104563609448670518081918257
q − 1 = 233 × 3 × 5179 × 216901160674121772178243990852639108850176422522235334586122689
r − 1 = 232 × 32 × 463 × 539204044132271846773 × 8999194758858563409123804352480028797519453
s − 1 = 232 × 32 × 1709 × 24859 × 1690502597179744445941507 × 10427374428728808478656897599072717

Cycles of Elliptic Curves

Posted on by John

The previous post gave two examples of pairs of elliptic curves in which

#(E / Fp) = q

and

#(E / Fq) = p.

That is, the curve E, when defined over integers mod p has q elements, and when defined over the integers mod q has p elements.

Pairs

Silverman and Stange [1] call this arrangement an amicable pair. They found a small pair of amicable elliptic curves:

y² = x³ + 2

with p and q equal to 13 and 19. They give many other examples, but this one is nice because it’s small enough for hand calculations, unlike the curves mentioned in the previous post that had on the order of 2254 elements.

Cycles

More generally, amicable curve pairs are amicable curve cycles with cycle length 3. Silverman and Stange give this example of a cycle of length 3:

y² = x³ − 25x − 8

with (p, q, r) = (83, 79, 73). That is, the curve over F83 has 79 elements, the curve over F79 has 73 elements, and the curve over F73 has 83 elements.

The authors show that there exist cycles of every length m ≥ 2.

Application

Why does any of this matter? Cycles of elliptic curves are useful in cryptography, specifically in zero-knowledge proofs. I hope to go into this further in some future post.

Confirmation

The curves mentioned above are small enough that we can compute the orders of the curves quickly by brute force. The following Python code confirms the claimed orders above.

def order(eqn, p):
    c = 1 # The point at infinity
    for x in range(p):
        for y in range(p):
            if eqn(x, y) % p == 0:
                c += 1
    return c

eqn = lambda x, y: y**2 - x**3 - 2
assert( order( eqn, 13) == 19 )
assert( order( eqn, 19) == 13 )

eqn = lambda x, y: y**2 - x**3 + 25*x + 8
assert( order( eqn, 83) == 79 )
assert( order( eqn, 79) == 73 )
assert( order( eqn, 73) == 83 )

Related posts

[1] Joseph H. Silverman and Katherine E. Stange. Amicable pairs and aliquot cycles for elliptic curves. Experimental Mathematics, 20(3):329–357, 2011.

Pallas, Vesta, and Zcash

Posted on by John

Yesterday’s post mentioned Tweedledum and Tweedledee, a pair of elliptic curves named after characters in Lewis Carroll’s Through the Looking Glass.

Zcash uses a very similar pair of elliptic curves for zero-knowledge proofs: Pallas and Vesta. One named after a Greek goddess associated with war, and one named after a Roman goddess associated with home and hearth. (Zcash used the Jubjub curve, also mentioned yesterday, though not in the most recent release.)

The curves Pallas and Vesta are collectively known as the “pasta” curves, pasta being a portmanteau of pallas and vesta.

pa(llas ve)sta

Tweedledum, Tweedledee, Pallas, and Vesta all have the equation

y² = x³ + 5

over different prime-order fields.

The number of elements in Tweedledum’s field equals the number of elements in Tweedledee’s elliptic curve, and vice versa. The same relationship holds between Pallas and Vesta. And all four curves have roughly 2254 points.

If p is the size of Tweedledum’s field (and Tweedledee’s curve), and q is the size of Tweedledee’s field (and Tweedledum’s curve),

p = 2254 + 4707489545178046908921067385359695873
q = 2254 + 4707489544292117082687961190295928833

If p is the size of Pallas’ field (and Vesta’s curve), and q is the size of Vesta’s field (and Pallas’ curve),

p = 2254 + 45560315531419706090280762371685220353
q = 2254 + 45560315531506369815346746415080538113

Note that while Tweedledum and Tweedledee, and Pallas and Vesta, are “pairs” of curves used together, but they do not form a pairing in the technical sense of that word.

Lewis Carroll and Zero Knowledge Proofs

Posted on by John

Illustration from Through the Looking Glass

Elliptic curves are often used in cryptography, and in particular they are used in zero-knowledge proofs (ZKP). Cryptocurrencies such as Zcash use ZKP to protect the privacy of users.

Several of the elliptic curves used in ZKP have whimsical names taken from characters by Lewis Carroll. This post will look at these five elliptic curves:

  • Jubjub
  • Baby Jubjub
  • Bandersnatch
  • Tweedledee
  • Tweedledum

Charles Dodgson was a mathematician, and perhaps there’s some connection from his mathematical work to elliptic curves and ZKP, the connection explored here is with his literary works written under the name Lewis Carroll.

Jabberwocky names

The first three curves—Jubjub, Baby Jubjub, and Bandersnatch—all get their name from Lewis Carroll’s poem Jabberwocky.

“Beware the Jabberwock, my son!
The jaws that bite, the claws that catch!
Beware the Jubjub bird, and shun
The frumious Bandersnatch!”

These curves all have a twisted Edwards curve form and a Montgomery curve form, just like the relationship between Ed25519 and Curve25519 that I wrote about a few days ago.

As its name suggests, the Baby Jubjub elliptic curve is related to the Jubjub curve but smaller.

Bandersnatch is similar to Jubjub, but arithmetic over this curve can be implemented more efficiently.

Looking Glass names

The last two curves—Tweedledum and Tweedledee—take their names from Through the Looking Glass.

And as their names suggest, Tweedledum and Tweedledee and very closely related. Both have the equation

y² = x³ + 5

but over different fields. Tweedledum is defined over the integers mod p and has q elements. Tweedledee is defined over the integers mod q and has p elements. (Mind your ps and qs!)

Here

p = 2254 + 4707489545178046908921067385359695873
q = 2254 + 4707489544292117082687961190295928833

Note that Tweedledum and Tweedledee are a “pair” of curves used together, but they do not form a pairing in the technical sense of that word.

More Lewis Carroll posts

More elliptic curve posts