Deal of the Day

Home » Main » Manning Forums » 1998 » Implementing Elliptic Curve Cryptography

Thread: Urgent !! Help needed .!

Reply to this Thread Reply to this Thread Search Forum Search Forum Back to Thread List Back to Thread List

Permlink Replies: 71 - Pages: 5 [ 1 2 3 4 5 | Next ] - Last Post: Mar 29, 2009 4:27 PM by: drmike
Jaya_21

Posts: 39
Registered: 2/12/09
Urgent !! Help needed .!
Posted: Feb 12, 2009 1:55 PM
  Click to reply to this thread Reply

Hi !

I am new to this forum.
I just happened 2 look at this forum wen I ws browsing the net regarding my project.
Found this to be very nice.

I hav a lot of doubts. I really wish som1 clarifies all my doubts.

I m doing my Final B. Tech , Computer Science.
My final year project is about "Implementation of Elliptic Curve Cryptography on Smart Cards."

Concept of the project :
I will be using my smart cart for Signature Generation purpose. I ll run my Signature Generation algorithm on my smart card itself and see to it that the private key stored on my smart card never leaves the card.

I am not sure if I ll b showing a hardware implementation of it on my Smart Card.

I thought I ll initially simulate it in my sytem and then try something abt the Hw part.
I hav decided 2 code using JAVA ?

My doubts are as follows :

1) What is the difference between a prime field and binary field in implementation point of view ? Hw do I choose one ?

2 ) The Algorithm I got 4 ECDSA is as follows.
Key Generation :
1. Selection of an elliptic curve E over a finite field, say GF(p).
2. Selection of a point P(x,y) є GF of order n.
3. Selection of an unpredictable integer d in the range [1, n-1]. d : PRIVATE KEY.
4. Compute Q=dP.
5. The user's public key is (E, P, n, Q).

Signature Generation :
1. Select a random integer k in the range [1, n-1].
2. Compute (x1, y1) = kP = k(x,y).
Set r = x1 mod n. r = 0 => Step 1.
3. Compute k-1; mod n.
4. Compute s = k-1(h(m) + dr) mod n, where h is the hash value obtained from a suitable hash algorithm.
5. If s=0 , go to step 1.
6. Signature generated -(r, s).

Signature Verification :
1. Obtain an authentic copy of the public key (E, P, n, Q).
2. Verify that r and s are integers in the range [1, n-1].
3. Compute w = s-1 mod n and h(m).
4. Compute u1= h(m).w mod n ,
u2 = r.w mod n.
5. Compute u1P+u2Q = (x0 , y0) and v = x0 mod n.
6. Accept the signature if and only if v=r.

The algorithm is actually for a Prime field. Wil the same algo work 4 binary field ?

3) Hw do I fix my curve parameters ?

Thanks in advance.

Regards,
Jaya.

drmike


Posts: 543
Registered: 4/16/04
Re: Urgent !! Help needed .!
Posted: Feb 13, 2009 7:41 AM   in response to: Jaya_21 in response to: Jaya_21
  Click to reply to this thread Reply

You can use JAVA, but it's a touch harder because JAVA does not flip bits easily. There are several ECC classes written in JAVA though, so you might be able to get it done by using those. Here's one example: http://linux.softpedia.com/get/Programming/Libraries/jBorZoi-10600.shtml

The difference between prime field and polynomial is how fast your processor can crunch. In terms of security, they appear to be the same, but the more paranoid will choose the prime field because there are fewer places to attack it. For your application, the polynomial field should crunch faster because most smart cards don't have dedicated integer math units. If yours has a hardware multiply and divide, then the choice of prime field might make sense, otherwise take the polynomial field.

The algorithms work for both fields, it is the lowest level subroutines that perform the EC math that changes. And you use different curves for GF(p) and GF(2^n).

Your choice of curve depends on the level of security you require. You can take the NIST curves which are suggested for high security, or you can choose your own random curves and test them for the largest prime factor. Counting the number of points on an elliptic curve has turned into quite a science, and you should be able to find a math package that will do it for you. For your school project, it really doesn't matter, but you can at least write up your final report and explain what you would do in a real world situation.

Patience, persistence, truth,
Dr. mike

Jaya_21

Posts: 39
Registered: 2/12/09
Re: Urgent !! Help needed .!
Posted: Feb 14, 2009 1:20 AM   in response to: drmike in response to: drmike
  Click to reply to this thread Reply

Thnx a lot, Sir.
Wil start working with the input U had given.
Wil get back 2 U in case of doubts.
Expecting ur guidance throughout the project.

Regards,
Jaya.

Jaya_21

Posts: 39
Registered: 2/12/09
Re: Urgent !! Help needed .!
Posted: Feb 14, 2009 1:32 AM   in response to: Jaya_21 in response to: Jaya_21
  Click to reply to this thread Reply

Sir . . This s me , Jaya again.
U said "The algorithms work for both fields, it is the lowest level subroutines that perform the EC math that changes. And you use different curves for GF(p) and GF(2^n)."

Sir . . Can u please explain these lower level sub routines of binary fields in more detail?:
I am able to understand the flow of ECDSA in prime fields.
But I m getting stuck when it comes to binary fields.
I am not understanding the basics of binary fields clearly. Can U pls explain about it ? I am interested in fixing with binary fields. But I am not at all able to grasp ECDSA in binary fields.

drmike


Posts: 543
Registered: 4/16/04
Re: Urgent !! Help needed .!
Posted: Feb 14, 2009 5:19 PM   in response to: Jaya_21 in response to: Jaya_21
  Click to reply to this thread Reply

The fundamentals are explained in the book, the main difference is that for integers we fix the power of each term at 2^j. For polynomials, we let each term be x^j, and we don't set x=2. Since we don't care what x is, we have to be more careful with the algebra, but the essence is the same.

Suppose you have x^2+1 as your polynomial. All polynomials of powers higher than x can be broken down modulo x^2+1. So you would count 1, x, x^2 = 1, x^3 = x, x^4 = x^2 = 1, etc.

But things get more complicated when you use prime polynomials of higher powers. So x^192 + x^23 + 1 has a lot of terms (if it is primitive, it will have 2^192-1 terms, that's a lot!!) The book does explain this, and so do lots of other math books.

Jaya_21

Posts: 39
Registered: 2/12/09
Re: Urgent !! Help needed .!
Posted: Feb 17, 2009 7:15 AM   in response to: drmike in response to: drmike
  Click to reply to this thread Reply

Sir ,

1. I would like to know if it is possible to implement ECDSA ( Signature Generation algorithm alone ) using B -163 curve on a 8 bit microprocessor , 16F874 ( the processor of smart card ) ?
If it is not possible , which binary field curve will be suited for 8 bit processor implementation ?

2. These are the NIST parameters of P 192 curve .
p192X = "188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012"; (Base Point X )
p192Y = "07192b95ffc8da78631011ed6b24cdd573f977a11e794811"; ( Base Point Y)
p192B = "64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"; (b)
p192P = "6277101735386680763835789423207666416083908700390324961279"; (Prime modulus)
p192Order = "6277101735386680763835789423176059013767194773182842284081"; (Order of the curve)

How do I find "a" coefficient from the given parameters , Sir ?
I m using BigInteger package of Java.

3. In my project of Implementing ECDSA over Smart Cards , I am doing the s/w implementation as well as the hardware implementation. I hav chosen Prime field for Software implementation and Binary field for Hardware Implementation. The reason behind me choosing this is that I hav read in some papers that Prime field is suitable for S/w implementaion and binary field is suitable for h/w implementation. ( When I say h/w implementation , wat i mean is that I wil be using a Simulator s/w and use Embedded C for Coding ECDSA Signature generation algorithm ).
Am i making some sense , Sir ?

Thanks in advance,
Jaya.

drmike


Posts: 543
Registered: 4/16/04
Re: Urgent !! Help needed .!
Posted: Feb 17, 2009 7:48 AM   in response to: Jaya_21 in response to: Jaya_21
  Click to reply to this thread Reply

Yes, it is possible to implement on a PIC processor. It will be slow if you are not
careful.

On page 5 of this document: csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf you will find the formula for prime integer curves. It says

y^2 = x^3 - 3 x + b (mod p)

is their form of the curve. So a = 3 is fixed.

It makes sense to use binary curves on a smart card, but if you are going to use the same math on both the smart card and the PC, then they both have to use the same curves. If you are just doing a project and the smart card implementation has nothing to do with the PC version, then yes, it makes perfect sense.

Patience, persistence, truth,
Dr. mike

Jaya_21

Posts: 39
Registered: 2/12/09
Re: Urgent !! Help needed .!
Posted: Feb 17, 2009 12:36 PM   in response to: drmike in response to: drmike
  Click to reply to this thread Reply

Sir ,

Thanks a lot.
U are providing excellent guidance.Thanks a lot.

Sir . . I have a few more doubts.

1. As of today , has RSA taken an edge over ECC? Can U pls direct me to some recent papers which speaks about ECC vs RSA ?

2. Can better performance be achieved on Smart Cards with some cryptosystem other than ECC?

Thanks in advance ,
Jaya.

drmike


Posts: 543
Registered: 4/16/04
Re: Urgent !! Help needed .!
Posted: Feb 17, 2009 12:55 PM   in response to: Jaya_21 in response to: Jaya_21
  Click to reply to this thread Reply

Do a web search with "ecc vs rsa" and read the first 100 hits. I think you'll find that ECC is now considered far superior, and all crypto companies have some kind of ECC package.

Symmetric crypto will always be faster and more secure than public key crypto. The point of ECC is that you get more security with fewer bits, and thus with fewer transistors. It is cheaper and more secure, but not always faster. It can be made faster with the right choice of low level math and curve - and there is no loss of security.

The advantage of ECC public key crypto is that a person can use an easy to remember pass phrase which turns into an arbitrary key. With RSA, every key has to be a set of specific primes, and there is no easy way to remember them - the keys have to be stored on something. If you need public key crypto, ECC makes the most sense.

Jaya_21

Posts: 39
Registered: 2/12/09
Re: Urgent !! Help needed .!
Posted: Feb 17, 2009 1:14 PM   in response to: drmike in response to: drmike
  Click to reply to this thread Reply

Okay , Sir. I did google on ECC vs RSA. But all comparisons seem to be dated 2 to 3 yrs back. Now that U say , ECC does hav an edge ovr RSA , it s fine , Sir.

Sir . .

When I say B -163 (NIST Pseudo random Binary Curve ), it means the field is GF (2^163). It means the field has 2^ 163 elements and the elements are of size m.

Similarly , when I spk of P -192 ( NIST prime curve) , what does this 192 denote , Sir ?

Thanks ,
Jaya.

Jaya_21

Posts: 39
Registered: 2/12/09
Re: Urgent !! Help needed .!
Posted: Feb 17, 2009 1:19 PM   in response to: Jaya_21 in response to: Jaya_21
  Click to reply to this thread Reply

Sir . . Does that 192 denote the binary size representation of the integer 192 ?

Length of p in binary = 192 ?

Sir , also I would like to know the key size when I use a Pxxx NIST Curve ? Is it something like half the field length size ?

drmike


Posts: 543
Registered: 4/16/04
Re: Urgent !! Help needed .!
Posted: Feb 17, 2009 3:35 PM   in response to: Jaya_21 in response to: Jaya_21
  Click to reply to this thread Reply

Yes, the numbers indicate the ECC base field size, so you need that many bits to do the calculations. That is NIST nomenclature.

For B-xxx fields, they use a polynomial basis. For K-xxx fields, they use a normal basis (and they chose optimal field sizes so the math can be done fast). For P-xxx fields, they use prime integer basis (regular modular math).

In all these cases, ECC takes about half the field to guess a key. In a symmetric key you need the whole field. The main purpose of public key crypto is to send a symmetric key, so to ensure security, you need twice as many bits in the public key as in the symmetric key. So a 64 bit symmetric key can be hidden with a 128 bit ECC key. Here's a quote from: http://en.wikipedia.org/wiki/Key_size

"As of 2003[update] RSA Security claims that 1024-bit RSA keys are equivalent in strength to 80-bit symmetric keys, 2048-bit RSA keys to 112-bit symmetric keys and 3072-bit RSA keys to 128-bit symmetric keys. RSA claims that 1024-bit keys are likely to become crackable some time between 2006 and 2010 and that 2048-bit keys are sufficient until 2030. An RSA key length of 3072 bits should be used if security is required beyond 2030.[3] NIST key management guidelines further suggest that 15360-bit RSA keys are equivalent in strength to 256-bit symmetric keys." Taken from
here: http://csrc.nist.gov/publications/nistpubs/800-57/SP800-57-Part1.pdf

Computers have gotten a lot faster, but the math has not changed. ECC is more secure than RSA by a long shot. It just takes a little bit longer to fully appreciate.
Kind of like learning to drink scotch :-)

Jaya_21

Posts: 39
Registered: 2/12/09
Re: Urgent !! Help needed .!
Posted: Feb 17, 2009 10:40 PM   in response to: drmike in response to: drmike
  Click to reply to this thread Reply

Sir,

Thnk U.
What do U mean " ECC takes half the field size to guess the key. " ?

Regards,
Jaya.

drmike


Posts: 543
Registered: 4/16/04
Re: Urgent !! Help needed .!
Posted: Feb 18, 2009 8:05 AM   in response to: Jaya_21 in response to: Jaya_21
  Click to reply to this thread Reply

It comes from the methods used to crack P = k*G. If you know G and P, you must guess at least the square root of the number of points on average to find k. So if your field size is 2^n, you must guess 2^(n/2) points.

If you have a 64 bit symmetric key, it takes 2^63 guesses to crack it on average. So to protect a symmetric key, you need twice as many bits or n=128 on the elliptic curve.

For some interesting reading on how to crack ECC, look here: http://cristal.inria.fr/~harley/ecdl7/

Jaya_21

Posts: 39
Registered: 2/12/09
Re: Urgent !! Help needed .!
Posted: Feb 18, 2009 11:32 AM   in response to: drmike in response to: drmike
  Click to reply to this thread Reply

Thnk U , Sir.

When binary fields are used , v spk about polynomials.
Where are these polynomials actually used in basic math operations ?

Legend
Gold: 300 + pts
Silver: 100 - 299 pts
Bronze: 25 - 99 pts
Manning Author
Manning Staff
Manning Developmental Editor