Posts:
39
Registered:
2/12/09



Urgent !! Help needed .!
Posted:
Feb 12, 2009 1:55 PM


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, n1]. 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, n1]. 2. Compute (x1, y1) = kP = k(x,y). Set r = x1 mod n. r = 0 => Step 1. 3. Compute k1; mod n. 4. Compute s = k1(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, n1]. 3. Compute w = s1 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.


Posts:
543
Registered:
4/16/04



Re: Urgent !! Help needed .!
Posted:
Feb 13, 2009 7:41 AM
in response to:
Jaya_21


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/jBorZoi10600.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


Posts:
39
Registered:
2/12/09



Re: Urgent !! Help needed .!
Posted:
Feb 14, 2009 1:20 AM
in response to:
drmike


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.


Posts:
39
Registered:
2/12/09



Re: Urgent !! Help needed .!
Posted:
Feb 14, 2009 1:32 AM
in response to:
Jaya_21


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.


Posts:
543
Registered:
4/16/04



Re: Urgent !! Help needed .!
Posted:
Feb 14, 2009 5:19 PM
in response to:
Jaya_21


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^1921 terms, that's a lot!!) The book does explain this, and so do lots of other math books.


Posts:
39
Registered:
2/12/09



Re: Urgent !! Help needed .!
Posted:
Feb 17, 2009 7:15 AM
in response to:
drmike


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.


Posts:
543
Registered:
4/16/04



Re: Urgent !! Help needed .!
Posted:
Feb 17, 2009 7:48 AM
in response to:
Jaya_21


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


Posts:
39
Registered:
2/12/09



Re: Urgent !! Help needed .!
Posted:
Feb 17, 2009 12:36 PM
in response to:
drmike


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.


Posts:
543
Registered:
4/16/04



Re: Urgent !! Help needed .!
Posted:
Feb 17, 2009 12:55 PM
in response to:
Jaya_21


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.


Posts:
39
Registered:
2/12/09



Re: Urgent !! Help needed .!
Posted:
Feb 17, 2009 1:14 PM
in response to:
drmike


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.


Posts:
39
Registered:
2/12/09



Re: Urgent !! Help needed .!
Posted:
Feb 17, 2009 1:19 PM
in response to:
Jaya_21


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 ?


Posts:
543
Registered:
4/16/04



Re: Urgent !! Help needed .!
Posted:
Feb 17, 2009 3:35 PM
in response to:
Jaya_21


Yes, the numbers indicate the ECC base field size, so you need that many bits to do the calculations. That is NIST nomenclature.
For Bxxx fields, they use a polynomial basis. For Kxxx fields, they use a normal basis (and they chose optimal field sizes so the math can be done fast). For Pxxx 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 1024bit RSA keys are equivalent in strength to 80bit symmetric keys, 2048bit RSA keys to 112bit symmetric keys and 3072bit RSA keys to 128bit symmetric keys. RSA claims that 1024bit keys are likely to become crackable some time between 2006 and 2010 and that 2048bit 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 15360bit RSA keys are equivalent in strength to 256bit symmetric keys." Taken from here: http://csrc.nist.gov/publications/nistpubs/80057/SP80057Part1.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


Posts:
39
Registered:
2/12/09



Re: Urgent !! Help needed .!
Posted:
Feb 17, 2009 10:40 PM
in response to:
drmike


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


Posts:
543
Registered:
4/16/04



Re: Urgent !! Help needed .!
Posted:
Feb 18, 2009 8:05 AM
in response to:
Jaya_21


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/


Posts:
39
Registered:
2/12/09



Re: Urgent !! Help needed .!
Posted:
Feb 18, 2009 11:32 AM
in response to:
drmike


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

