Eliptic Curves Cryptography over GF(p^3)

Martyr

There was a crackme challenge written by a reverser "WiteG" early last year
based on Eliptic Curve Nyberg-Rueppel signature scheme.

The challenge was to write a valid key generator and was solved shortly afterwards by a cracker "jb"

The solution jb gives is:

Signature generation over GF(p^3).

The serial is entered using base64 charset. It is composed of two parts
r and s, of 64 bits. Two points P and Q are taken on the field, such as
Q=d*P. The field is of order n=FFFCCDE18D3CA8AB.
The name is hashed using among other MD5, to generate a 64 bit string h.

Signature verification:

---

Verify that r and s are integers in the interval [0, n-1].
Compute h = Hash(name)
Compute X = r*P + s*Q
If X = infinite point then reject the signature
Convert the x-coordinate of X to an integer x, and compute v = x mod n
If r - x = h accept the signature,
else reject the signature.

The DLP has been computed using Pollard's Rho algorithm. The implementation
has been done in C using Miracl. It took about 7 hours to find d such as
Q = d*P. I wrote an other implementation using Maple, but is was damn slow.
It would have taken something like three weeks.
Finally d = 1F1B2BB3135CFB06
Now it is easy to generate a valid signature:

Signature generation:

---

Select k in [1, n-1]
Compute k*P = (x1, y1) and convert x1 to an integer x.
Compute r = x + h mod n
Compute h = Hash(name)
Compute s = (k-r) * d^(-1) mod n
Return (r, s)

Some quick explanations:
We want : r - x = h, ie : x = r - h
Let take k a random number. We want :
absc(k*P) = absc(r*P * s*Q) = r - h
So :
. r = h + absc(k*P)
. absc(r*P * s*Q) = absc((r + s*d)*P)
= absc(k*P)
So k = r + s*d mod n
That gives : d = (k-r)^(-1) mod n

I don't check if s = 0 in the keygen, it would be really bad luck

I would like to be able to solve puzzles like these in future..i just find
it really interesting,but regretable to say my knowledge of mathematics is very poor.
I've never been a fan of mathematics, unfortunatly left school at an early age
and didn't learn enough about the subject since then.

Now, i appreciate the value of the subject more since i want to understand
how to crack these puzzles and mathematics is essential in doing that.
I am willing to learn. But probably only the "need to know" details until later on..or is this the wrong attitude to have?

Learning specifically, branches of the subject which would help me understand different cryptosystems based on mathematical equations.

From a reverse-engineering perspective, i can read assembly, but it is when trying to understand "complex" arithmetic, i end up just damn confused!
i quote complex because it probably isn't for some of you here..

Anyway, learning more math would obviously help me in this area.

so, what branches of mathematics should i learn about in order to understand
the eliptic curves cryptosystem better, and others like it?
such as ElGamal,LUC,RSA,Rabin..etc

also, based on vague comments WiteG has made, i am assuming that there is
more than 1 valid signature generation algorithm to solve his crackme
is this possible, or am i way off the mark here??

any feedback, negative or positive is welcome.

thanks.

Professor_Fink

Average Joe wrote:

Anyway, learning more math would obviously help me in this area.

so, what branches of mathematics should i learn about in order to understand
the eliptic curves cryptosystem better, and others like it?
such as ElGamal,LUC,RSA,Rabin..etc

This all lies in an area of mathematics known as number theory. Basically, I'd recommend you take out a book from the library on it. Read up on Fermat's little theorem (the basis for RSA), discrete logs (the basis for El Gamal), diophantine equations etc.

It seems extremely unlikely that you'll crack RSA or El Gamal, as the one way functions upon which these are based are extremely well studied.

Delphi91

Professor_Fink wrote:

This all lies in an area of mathematics known as number theory. Basically, I'd recommend you take out a book from the library on it. Read up on Fermat's little theorem (the basis for RSA), discrete logs (the basis for El Gamal), diophantine equations etc.

It seems extremely unlikely that you'll crack RSA or El Gamal, as the one way functions upon which these are based are extremely well studied.

Have a look at "The Code Book" by Simon Singh - it's highly readable and gives a great insight into codes from Roman times up to present day cryptography.

You could read it after you've read his other book on Fermat - "Fermats Last Theorem".

Mike

Professor_Fink

Delphi91 wrote:

Have a look at "The Code Book" by Simon Singh - it's highly readable and gives a great insight into codes from Roman times up to present day cryptography.

You could read it after you've read his other book on Fermat - "Fermats Last Theorem".

Mike

The code book is an excellent pop science crypto book, but if you are interested in mathematical attacks on modern crypto systems I would suggest 'Introduction to Number Theory' followed by 'Cryptography: Theory and Practice'.

Professor_Fink

Oh, and Applied Cryptography by Bruce Schneier is a no-brainer.

Martyr

thanks for response, i'll probably check out both these books.

Professor_Fink wrote:

It seems extremely unlikely that you'll crack RSA or El Gamal, as the one way functions upon which these are based are extremely well studied.

WiteG also wrote a crackme using RSA years ago, it hasn't been keygen'd yet.

WiteG wrote:

Who said that coding a working RSA-1920 protection in pure asm is hard ? CrackMe 5 is a very good example of uncrackable crackme (atm ). Incredibly slow and simple implementation.

crackmes

Professor_Fink

Let me just clarify: There may well be problems with specific implimentations of RSA (and Cryptography: Theory and Practice covers quite a few), but the actual RSA algorithm appears sound.

And by 'appears sound' I mean that the best known attack on it is impracticle for large key sizes (>640 bits at the moment). Of course some intelligence agence may have a better attack, but they're not likely to make it public.

It's also based on a problem that has been known for hundreds of years, and studied by Gauss and Fermat among others, and remains unsolved.