This topic is READ ONLY
Jaya_21 (39) [Avatar] Offline
#1
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 (543) [Avatar] Offline
#2
Re: Urgent !! Help needed .!
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 (39) [Avatar] Offline
#3
Re: Urgent !! Help needed .!
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 (39) [Avatar] Offline
#4
Re: Urgent !! Help needed .!
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 (543) [Avatar] Offline
#5
Re: Urgent !! Help needed .!
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 (39) [Avatar] Offline
#6
Re: Urgent !! Help needed .!
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 (543) [Avatar] Offline
#7
Re: Urgent !! Help needed .!
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 (39) [Avatar] Offline
#8
Re: Urgent !! Help needed .!
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 (543) [Avatar] Offline
#9
Re: Urgent !! Help needed .!
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 (39) [Avatar] Offline
#10
Re: Urgent !! Help needed .!
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 (39) [Avatar] Offline
#11
Re: Urgent !! Help needed .!
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 (543) [Avatar] Offline
#12
Re: Urgent !! Help needed .!
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 smilie
Jaya_21 (39) [Avatar] Offline
#13
Re: Urgent !! Help needed .!
Sir,

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

Regards,
Jaya.
drmike (543) [Avatar] Offline
#14
Re: Urgent !! Help needed .!
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 (39) [Avatar] Offline
#15
Re: Urgent !! Help needed .!
Thnk U , Sir.

When binary fields are used , v spk about polynomials.
Where are these polynomials actually used in basic math operations ?
drmike (543) [Avatar] Offline
#16
Re: Urgent !! Help needed .!
The lowest level. So the curve is at the lowest level, and so are it's coefficients. The points on the curve become the next level. The addition of points is a higher level of abstraction. When adding two points you get another point on the curve. But to do the addition, you must perform a lot of lower level math.

Polynomials are also used for error correction codes, like those used on DVD's (Reed-Solomon codes). So binary fields and polynomial math are widely used in engineering applications. The math is not that hard really, but it can be abstract. Keeping track of which math is doing what tends to get confusing, so I like to go slow and make sure I'm using binary fields, prime factors and point addition at the correct time.
Jaya_21 (39) [Avatar] Offline
#17
Re: Urgent !! Help needed .!
Okay , Sir. Thnk U.

I would lik 2 kno about different variations of the ECDSA algorithm.
Can U pls explain them to me and provide me links for papers and materials about these variations ?

Thanks in advance ,
Jaya.
drmike (543) [Avatar] Offline
#18
Re: Urgent !! Help needed .!
I describe two signature schemes in the book. But you can look here:
http://csrc.nist.gov/groups/ST/toolkit/digital_signatures.html
to find out what the present standard is in the USA.

For ECDSA there is only one method that is not patented, the NR scheme is. I'm not sure when that patent expires though, so it may be ok to use it now. Other than that, I don't know of any other elliptic curve versions.
Jaya_21 (39) [Avatar] Offline
#19
Re: Urgent !! Help needed .!
But Sir , is thr any chance of improvising the performance of the algorithm by making some changes in any of the steps (like scalar multiplication) ?

Right now I hav implemented the "Double and Add" method for scalar multiplication. Something more better Sir?

Can variations be thought about in this angle Sir?

Sir. . I hav successfully completed ECDSA Java implementation for NIST prime curves. What % of effort will be needed to convert the code to wrk well for binary B 163 curve? Really scared of this binary stuff. But we are asked in the college to come out with binary implementation also. smilie

Thnx in advance,
Jaya.
drmike (543) [Avatar] Offline
#20
Re: Urgent !! Help needed .!
It's not that scary if you take your time and learn a few basics. The elliptic curve stuff is really deep, but you don't need to know as much as a professor of mathematics!

The main place to start is chapter 3. This was written for people who have no knowledge of this kind of math. My sons are learning polynomials in high school, I'm sure you have all the math you need. It is just learning how to apply it in a new way.

Relax - math is fun. Not scary! smilie
Jaya_21 (39) [Avatar] Offline
#21
Re: Urgent !! Help needed .!
Sir,
I dont hav ur book. Whr do I get it ? Because , I dont hv a credit card I wil not b able to make online transactions also. smilie
Wil U pls get me the details of buying ur book , Sir ?
drmike (543) [Avatar] Offline
#22
Re: Urgent !! Help needed .!
You will have to go to a local book store and order it. They can get it from an online store for you. There are many book stores online in India, I am certain there are many ways to get it! If you really want to learn this, it will be a good way to start.

Besides, you can find many other books online this way, and then have the local book store order it for you. If there is no local library, it is a way to make your own smilie
Jaya_21 (39) [Avatar] Offline
#23
Re: Urgent !! Help needed .!
Yes , Sir.
I am trying to get the book. smilie
Thank U.
Jaya_21 (39) [Avatar] Offline
#24
Re: Urgent !! Help needed .!
Sir ,

I would like to know the different methods of implementing Scalar Multiplication.
Can U please direct me to some papers dealing with those different methods?

Thanks in advance,
Jaya.
drmike (543) [Avatar] Offline
#25
Re: Urgent !! Help needed .!
I think you mean "modular multiplication". A web search on that will get you some good papers:
www.vlsi.informatik.tu-darmstadt.de/staff/laue/publications/crash2005_slides.pdf
and
http://www.informatica.si/PDF/30-1/10_Nedjah-A%20Review%20of%20Modular%20Multiplication%20Methods%20and...pdf
both look like good reviews.
Jaya_21 (39) [Avatar] Offline
#26
Re: Urgent !! Help needed .!
Sir . . I donno what modular multiplication means.
Referred to the papers U had suggested.

I am asking about the different methods of doing kP (k , an integer and P, a point on the curve). This is what I meant as scalar multiplication, Sir.

For example , the Double and Add Method. I am asking for similar such methods Sir.

Sir . . then U had told me that there does not exist any variations as such for ECDSA algorithm. Okay , Sir.
How about improvisations suggested for the algorithm?

Thanks,
Jaya.

Message was edited by:
Jaya_21
drmike (543) [Avatar] Offline
#27
Re: Urgent !! Help needed .!
OK, I see. I guess I call that "point multiplication". I describe a couple of methods in the book based on several papers of the time. But here is a recent paper you might find very interesting (I sure do!):
http://eprint.iacr.org/2008/390
"Elliptic Curve Cryptography: The Serpentine Course of a Paradigm Shift"

There are discussions about different digital signature schemes and multiplication methods.

Another good web page is this one: http://www.isg.rhul.ac.uk/~sdg/ecc.html
Look at Edwards curves for alternative methods that is more recent.
Jaya_21 (39) [Avatar] Offline
#28
Re: Urgent !! Help needed .!
Okay Sir.

This question is not about ECC. But then I am putting it across U.


Sir. . If U remember , I had told U long back that our project is about smart cards.
We browsed and found the architecture of smart card , the PIC used , etc and all that Sir.

We are going to implement the ECDSA Signature Generation algorithm on the 16F874 processor. Basically V wil be running the algo on that processor.
Language used : Embedded C
IDE : MP Lab

My teacher here had asked to browse and check out as to how the security of the smart card can be improvised.
Now , how do we brinng in security ascepts here , Sir ?
How do we handle hardware and software attacks on the smart card?
How do we illstrate it in our project , Sir ?

Thanks in advance,
Jaya.
drmike (543) [Avatar] Offline
#29
Re: Urgent !! Help needed .!
Jaya_21 (39) [Avatar] Offline
#30
Re: Urgent !! Help needed .!
Thanks a lot , Sir.
Jaya_21 (39) [Avatar] Offline
#31
Re: Urgent !! Help needed .!
Sir . . Can U please explain me the SHA -1 algorithm ?
I am able to understand it only till the step in which the five 32 bit registers are initialised.
What happens next ?
I am not able to understand what is given in the books , Sir.
Probably a lil bit of input from U would help I guess.
Help , pls !!!

Thanks in advance,
Jaya.
drmike (543) [Avatar] Offline
#32
Re: Urgent !! Help needed .!
Have you looked at the Wikipedia page?
http://en.wikipedia.org/wiki/SHA_hash_functions
There are some nice pictures there. There are lots of references too, and I bet the papers on cryptanalysis will all have very good references as well. The cryptanalysis papers are good to read for full understanding because they have to explain how things work in detail so people can understand how their attack will defeat how it works.

Patience, persistence, truth,
Dr. mike
Jaya_21 (39) [Avatar] Offline
#33
Re: Urgent !! Help needed .!
Thanks a lot , Sir.
I got it. smilie
Jaya_21 (39) [Avatar] Offline
#34
Re: Urgent !! Help needed .!
Sir . .

Can U please let me know about JavaCard technology ?
drmike (543) [Avatar] Offline
#35
Re: Urgent !! Help needed .!
I've never heard of it before. But a quick web search gives me:
http://en.wikipedia.org/wiki/Java_Card

I prefer assembler and VHDL myself, but it looks like it has been used for over 10 years now, so it should have most of the bugs out and be very stable.
Jaya_21 (39) [Avatar] Offline
#36
Sir . . Help please .!
Sir . .

We had our project review yesterday and we were screwed up when we said we will be writing ECDSA signature generation algorithm on the 16F84A processor ( which wil be used on the smart card ). They shouted that U wil not be able to do this , that , bla , bla . . . smilie

Sir . .Wil U pls help me ??
Can U please direct me to some "Embedded C" code for ECDSA that would run on the PIC 16F84A ?
Field : 2^163.

Please , Sir. In a pathetic state . smilie

Thanks in advance,
Jaya.
drmike (543) [Avatar] Offline
#37
Re: Sir . . Help please .!
Well, it won't be easy! The PIC16F84A only has 68 bytes of ram. Here is the datasheet on Microchip's web page: http://www.microchip.com/wwwproducts/Devices.aspx?dDocName=en010230

For 2^163 you need 21 bytes for each element. You can have one x and one y value and that takes up 42 bytes - a full 2/3 of your ram. So to add two points you need 84 bytes just to hold the x and y values.

I suggest you cut back on the field size and make it something that only uses 8 bytes per x or y. Then you have room to hold two x and y values (32 bytes) plus a few temporary variables (another 16 to 24 bytes) so you are at 56 bytes. The rest can be used for counters.

I don't think you can program that in C, you will have to do it in assembler. C requires a stack for subroutines, and that chews up memory space which you need to hold your variables. Fortunately the PIC is very easy to program in assembler and all the tools for it are free.

Good luck!
Patience, persistence, truth,
Dr. mike
Jaya_21 (39) [Avatar] Offline
#38
Re: Sir . . Help please .!
Sir ,

Then in many papers it is said that ECC is implemented on smart cards. Smart card has an 8 bit processor only na Sir ?

In case of assembler coding , whuch tool should i use ?

Is the code available somwhere over the net ?

Thanks,
Jaya.
drmike (543) [Avatar] Offline
#39
Re: Sir . . Help please .!
Yes, the tools for that chip are free:
http://www.microchip.com/stellent/idcplg?IdcService=SS_GET_PAGE&nodeId=1406&dDocName=en019469&part=SW007002

Download the MPLAB IDE. You can either purchase a programmer or build your own, they tell you how. They also have manuals for the assembler there.
Jaya_21 (39) [Avatar] Offline
#40
Re: Sir . . Help please .!
Sir . .
Please check out the following website.

http://www.starwafer.com/pic16f84+24lc16eng.htm

This is the architecture of the smart card we had chosen for our project.
Is this okay , Sir ?
Is it possible to just implement the ECDSA - Sign generation algorithm alone on this 16F84 processor with the aid of the 24LC16 EEPROM using Embedded C, Sir ?

If yes , can U pls give us more suggestions on working with this architecture ?

Thanks in advance,
Jaya.
Jaya_21 (39) [Avatar] Offline
#41
Re: Sir . . Help please .!
Sir ,

Can U pls tell me about the time complexity and space complexity of running the ECDSA - Sign generation algorithm on the 8 bit processor specified above ?
drmike (543) [Avatar] Offline
#42
Re: Sir . . Help please .!
It will be very difficult if you don't program in assembler. It says
"1024 X 14 On-Chip Program Momery " (that o should be an e smilie

1k of program memory is very very small. To do the point addition algorithm requires some complicated addition, multiplication and division of long polynomials. Even if you cut the size of the fields back to 8 bytes each, you still have to execute the program.

The extra rom space is good for data storage, so you can save lots of data. But you don't have a lot of room for code. I would suggest looking at how you do the math for a specific curve. You can find all the fixed data you need (there are many lookup tables you can use and you have room to store them) but you need to figure out what the code has to do. Then figure out if it will fit.

If you do it in C, my bet is it can't be done. You don't have enough ram for C to work. But in assembler it might be possible.

The Silver card is much better - it has 8k words of program memory and 368 bytes of ram. If you can switch to that card, then your life will be much easier since C will probably work with that card.
drmike (543) [Avatar] Offline
#43
Re: Sir . . Help please .!
I don't know what it will take - you will have to figure that out by going through the details. The time and space complexity depends on how you write your code - you can take less time by using a lot more lookup tables (more space), but the original device you picked has very little ram or rom and the external memory would be very slow. If you can switch to the Silver card I bet you can make things work and it will be much easier since you can program that in C.
Jaya_21 (39) [Avatar] Offline
#44
Re: Sir . . Help please .!
Sir . .

Actually this is what we thought of doing.

1 . Write Embedded C code for ECDSA Sign Generation in MPLAB IDE.

2 . Compile it , run it , then port the "hex" code to the processor.

We wil not move the C code directly to the proceesor. We will be moving the hex file only.
Now is it okay , Sir ? Can things be done ?
drmike (543) [Avatar] Offline
#45
Re: Sir . . Help please .!
Maybe. It is still difficult, but not impossible. I think the first thing to do is to get the code and compare some C code that does the basic math with hand written assembler. Once you see the difference, and look at how much ram and rom is available, you will have a much better idea on how things will fit.

There are several levels of math - make sure the lowest level works since that is the most important. From there, most of what you will do will be calling the low level routines in different order, and the rom space will not be much. But that depends on how the C uses ram and rom - many embedded compilers are pretty darn smart. It should be possible - but it will not be easy!!! Make sure you take enough time to double check every subroutine you write.
Jaya_21 (39) [Avatar] Offline
#46
Re: Sir . . Help please .!
Okay , Sir.

Sir . . Is there any embedded C code readily available in the net for implementing ecdsa algo ?
drmike (543) [Avatar] Offline
#47
Re: Sir . . Help please .!
I don't know about embedded, but there are a few examples if you just to a web search on "ecdsa C". It won't take much to transform them into embedded code.
Jaya_21 (39) [Avatar] Offline
#48
Re: Sir . . Help please .!
Okay , Sir.

I hav personally done a ECDSA implementation for prime fields in JAVA.
But my project demanded me to do it in binary fileds.
So I am working on it now.
I thought ECDSA on binary fields and prime fields are totally different. Atleast the lower level math operations. . . .
But i found the code 2 be the same for binary and prime fields 2 be the same in the code found in the following link.

http://jopsen.dk/blog/2007/12/simpleecdsa-a-simple-implementation-of-ecdsa-in-c/

What does this mean , Sir ?

Where hav I not understood properly , Sir ?
drmike (543) [Avatar] Offline
#49
Re: Sir . . Help please .!
It is integer based, not polynomial field based. The "binary" may refer to the resultant code, not the field type.

Check out this paper: http://www.liafa.jussieu.fr/~cf/M2/palm.pdf
It lists the operations in pseudo code, converting it to JAVA should be straight forward.

Patience, persistence, truth,
Dr. mike
Jaya_21 (39) [Avatar] Offline
#50
Re: Sir . . Help please .!
Sir ,

I thought this is how ECDSA should be done for binary fields.
Please correct me wherever I am wrong.

INITIAL SETUP :

Step 1 :

My polynomial is x^4 + x + 1.
Field = 2^4.
Let g be the root of the polynomial.

So , I construct the following table.

x^3---x^2---x^1---x^0

g^0--- 0 0 0 1
g^1--- 0 0 1 0
g^2--- 0 1 0 0
g^3--- 1 0 0 0
g^4--- 0 0 1 1 ( x^4 = x + 1 => g^4 = g + 1 )
g^5--- 0 1 1 0 ( g^5 = g . g^4 = g (g + 1) = g^2 + g )
g^6--- 1 1 0 0 ( g^6 = g. g^5 = g ( g^3 + g^2 ) = g^4 + g^3 = g^3 + g + 1 )
.
.
g^10--- 0 1 1 1
.
g^15


Step 2 :

Generate points on the curve.
y^2 + xy = x^3 + g^4 x^2 + 1

x ranges from g^0 to g^ 15.
for every x , compute LHS.
Vary y from g^0 to g^15 and compute RHS.

Whenever LHS = RHS , output the point.

So , now I hav a set of points on the curve.

KEY GENERATION :

Step 3 :

Choose the base point , P.
Select a random number , d.
dP. (d = 9)

dP is done as this.
P + P + P + . . . . + P ( d times )
Formula relevant to compute slope and (x3 , y3 ) were taken from chapter 5 of ur book , Sir.

SIGNATURE GENERATION :

Step 4 :

Choose k.
kP.
For example , if kP = (g ^ 10 , g ) , compute r.
r = g ^ 10 =0111 ( from table ) = 7
Assume h(m) = 10.
s = K-1 ( h(m) + d.r)
= ( 10 ) -1 (10 + 9.7) ( 10 =g^9 is taken from table )
= (g^9 ) -1 (73)
= g^ (-9) . 73
= g ^ 6 .73
= (1100) . 73 ( g^6 = 1100 is taken from the table )
= 12 . 73
= 576
= 576 % 16
= 12

(r,s) = (7,12)

SIGNATURE VERIFICATION

Step 5 :

Do watever steps are needed following the above logic.


Sir. . . This is how I understand working in polynomial field.
Can I proceed my Embedded C coding with this understanding , Sir ?
Please , please correct me Sir.
drmike (543) [Avatar] Offline
#51
Re: Sir . . Help please .!
The basics are correct. But be careful with the details!

g^0--- 0 0 0 1
g^1--- 0 0 1 0
g^2--- 0 1 0 0
g^3--- 1 0 0 0

that's all obvious and correct.

g^4--- 0 0 1 1 ( x^4 = x + 1 => g^4 = g + 1 )
yes
g^5--- 0 1 1 0 ( g^5 = g . g^4 = g (g + 1) = g^2 + g )
yes
g^6--- 1 1 0 0 ( g^6 = g. g^5 = g ( g^3 + g^2 ) = g^4 + g^3 = g^3 + g + 1 )
The 1100 is right, but you wrote the answer for g^6 and put g^7th for where
g^6 is. Take your time and make sure your code creates the tables correctly.

It is a very, very good idea to do things by hand like this. It allows you to check your
code explicitly. Once you have all the bugs removed, it is much easier to go to
larger fields and be pretty sure you have the math correct. There may still be bugs,
but the general flow will be right.

Looks like you are on the right track. Good luck!
Jaya_21 (39) [Avatar] Offline
#52
Re: Sir . . Help please .!
Sir ,

I had typed that g^6 and g^7 wrongly by mistake.

Is the Sign Generation part of my previous reply correct , Sir ?

Step by step hav I proceeded properly , Sir ?
Jaya_21 (39) [Avatar] Offline
#53
Re: Sir . . Help please .!
Sir ,

Few more doubts.!!

1. Pls suggest me some logic to generate the points using C ? I did it manually. I really donno hw to proceed with C. Which data structure shall I use ? What LOGIC shall I go on with , Sir ?

2. Once my code works well with small fields, I hav decided to move on to the following field Sir.

Curve B-163 :
p(t) = t^163 + t^7 + t^6 + t^3 + 1
r = 5846006549323611672814742442876390689256843201587
b = 2 0a601907 b8c953ca 1481eb10 512f7874 4a3205fd
Base Points :
G x = 3 f0eba162 86a2d57e a0991168 d4994637 e8343e36
G y = 0 d51fbc6c 71a0094f a2cdd545 b11c5c0c 797324f1
When I start coding , should these base points ( hexadecimal format ) be converted to binary , then generator notation and then should I proceed with the generator and binary notation Sir ?

3. In JAVA, BigInteger package was available to deal Big numbers.
Hw can big numbers be stored in Embedded C , Sir ?
drmike (543) [Avatar] Offline
#54
Re: Sir . . Help please .!
On pages 271 and 272 I describe the DSA in detail, but you can also look at it here:
http://www.comms.scitech.susx.ac.uk/fft/crypto/ecdsa.pdf

The code in the book describes how to build structures in C, which should translate into JAVA. But you can find examples of the basic structures in my code as well:
http://www.eskimo.com/~eresrch and look at "field2n.h" and "polymain.c". This is designed to help people learn, so there are probably faster ways to do things.

Patience, persistence, truth,
Dr. mike
Jaya_21 (39) [Avatar] Offline
#55
Re: Sir . . Help please .!
Sir,

I hv ur " rosing_ecc_src_code " folder downloaded from the internet.
I am not able to understand the flow of ur code sir. Can U pls tel me which code is used for what Sir ?
Can U pls understand the flow of the program , Sir ?
Pls help me understand the follow of ur code , Sir.
drmike (543) [Avatar] Offline
#56
Re: Sir . . Help please .!
The code was written to help me write the book, and much of the code is now in the book. So the book does a better job describing things in detail. The essence is that every machine has different size, 8, 16, 32 or 64 bit data. So I tell the compiler how to set things up using WORDSIZE. The next most important number is NUMBITS, which is the number of bits used in the polynomial.

That didn't always work, so I set up ELEMENT as a fixed size. But really, it should be WORDSIZE, and the number of ELEMENTs in a FIELD2N depends on the if the machine is 8, 16 or 32 bits data size. For an 8 bit machine, you would define ELEMENT to be an unsigned char, and have enough of them to hold NUMBITS bits.

The simplest functions are rotate right and left as well as copy. The multiply is the first major function, and then there is the divide function which needs a few subroutines in its own right.

If you compile the code and test one subroutine at a time, it should go pretty quickly. For more detail, you'll need to get hold of the book.
Jaya_21 (39) [Avatar] Offline
#57
Re: Sir . . Help please .!
That didn't always work, so I set up ELEMENT as a fixed size. But really, it should be WORDSIZE, and the number of ELEMENTs in a FIELD2N depends on the if the machine is 8, 16 or 32 bits data size. For an 8 bit machine, you would define ELEMENT to be an unsigned char, and have enough of them to hold NUMBITS bits.

Sir . . I am nt able to explain this part of ur explanation.
Can U pls explain this in more detail with an example , Sir ?
drmike (543) [Avatar] Offline
#58
Re: Sir . . Help please .!
Here's the start of the file:

/*** field2n.h ***/

#define WORDSIZE (sizeof(char)*smilie <----- Do this
#define NUMBITS 134 <----- Change this EVERY TIME YOU CHANGE FIELD SIZE!!

Then the next lines in the file are:

#define NUMWORD (NUMBITS/WORDSIZE)
#define UPRSHIFT (NUMBITS%WORDSIZE)

#define MAXLONG (NUMWORD+1)

And a little later it has:

typedef unsigned char ELEMENT; <------ CHANGE THIS FROM WEB PAGE.

typedef struct {
ELEMENT e[MAXLONG];
} FIELD2N;

So NUMWORD depends on both NUMBITS (the size of your field) and WORDSIZE in this case 8 bits. You could just say

#define WORDSIZE 8

and be done. But note that ELEMENT is defined as the unsigned version of the WORDSIZE. For most machines, it will an 8 bit byte, 16 bit word or 32 bit long. Some machines may be a 64 bit double long (and some may be a "huge" 128 bits).

The point is that once you define WORDSIZE and ELEMENT, everything else should just go.
Jaya_21 (39) [Avatar] Offline
#59
Re: Sir . . Help please .!
Sir . .

As U said, I am stuck up with implementing ECDSA Sign generation on the 16f877 processor ( 8k program memory).

This is how I hav started with coding Sir.

#include<stdio.h>
#include<conio.h>

void print(int[]);
void find(int); // To find g^1,g^2. . .g^15 ( Binary array wil be returned.)
void print_index(int);
int find_ones(int[]);
void copy(int []);
int find_power(int[]);

int poly[5]={1,1,0,0,1},poly_element[4]={0,0,0,0},temp[4]={1,1,1,1},temporary[4]={0,0,0,0},ones[4],field_size=4;
int old[4]={1,1,0,0};

// Data Structure - Array of integers to hold the filed element

void main()
{
int i;

printf("

Field Polynomial :

");
print_index(field_size);
for(i=0;i<=4;i++)
printf(" %d",poly[i]);

printf("

Elements:
");
print_index(field_size-1);
for(i=0;i<=15;i++)
{
printf("

%d :",i);
find(i);
//print(poly_element);
}


printf(" Chk : %d",find_power(temp));
//sign_gen();
}

void find(int power)
{
int i,num_ones,j,k,p,q,r,m;

if(power<=field_size-1)
{
for(i=0;i<=3;i++)
{
if(i==power)
{
temporary[i]=1;
}
else
{
temporary[i]=0;
}
}
copy(temporary);
print(old);
}

if(power==field_size)
{
for(i=0;i<=3;i++)
{
temporary[i]=poly[i];
}
copy(temporary);
print(old);
}

if(power>field_size)
{

old[0]=1;
old[1]=1;
old[2]=0;
old[3]=0;

for(i=field_size+1;i<=power;i++)
{
for(m=0;m<=field_size-1;m++)
temporary[m]=0;

/* printf("

Finding %d :
",i);
printf("when a loop starts v hav the previous value
old -
");
print(old);
printf("
");
*/
num_ones=find_ones(old);

for(j=0;j<=num_ones;j++)
{
if(ones[j]+1<=3)
{
temporary[ones[j]+1]=1;
}

else
{
if(ones[j]+1==4)
{
for(p=0;p<=field_size-1;p++)
{

if(poly[p]==1)
{
if(temporary[p]==1)
{
temporary[p]=0;
}

else
{
temporary[p]=poly[p];
}
}
}
}

// printf("Intermediate after con chk
");
// print(temporary);



}
}

// printf("end of loop calculated
");
// print(temporary);
for(r=0;r<=field_size-1;r++)
old[r]=temporary[r];

// getch();
}//for i new
// print(old);
}
}

void print(int element[])
{
int i;

for(i=0;i<=field_size-1;i++)
{
printf(" %d",element[i]);
}
// printf("
");
}

void print_index(int n)
{
int i;
printf("
");
for(i=0;i<=n;i++)
printf(" %d",i);
}

int find_ones(int array[])
{
int i,cnt;

for(i=0;i<=field_size-1;i++)
ones[i]=0;
cnt=0;

for(i=0;i<=field_size-1;i++)
{
if(array[i]==1)
{
ones[cnt]=i;
cnt++;
}
}
return cnt-1;
}

void copy(int from_temp[])
{
int i;
for(i=0;i<=field_size-1;i++)
old[i]=from_temp[i];
}


int find_power(int array[])
{
int i,j,k,cnt,dec;

for(i=0;i<=15;i++)
{

find(i);


cnt=0;
for(j=0;j<=field_size-1;j++)
{
if(old[j]==array[j])
{
cnt++;
}
else
break;
}


if(cnt==field_size)
{
dec=0;
for(k=0;k<=field_size-1;k++)
dec+= (old[k]*2^k);
goto out;
}
}
out:
return i;
}

I hav not completed coding yet.. Just generated elements.
But the program memory is already half full.
The above code is for 2^4 field.
I need to do it for 2^ 163 in the same 16f877 processor.

Pls help me ,Sir.
What variations in my code will help me do it ?
drmike (543) [Avatar] Offline
#60
Re: Sir . . Help please .!
For one thing, you don't need the print statements. Just use a debugger to dump memory.

Once you get a subroutine working, look at the code the compiler generates and see if you can do better by hand. Saving a few bytes of code one subroutine at a time may be all it takes to get the whole thing to fit.

It takes a lot of hard work to make this fly. Details matter, and you need to learn the details of how the processor works, how the low level math works, and how the elliptic curve math works. What you are trying to do is very difficult, but not impossible. To be successful you need some confidence that you can work hard and make it happen.

So take things one step at a time. Get the rot_right and rot_left routines to work. Then get the negate routine to work. Then get all the one line subroutines to work (null, dblnull, copy, etc.) and then get poly_mul to work. As you add each routine, compress it as much as possible either by hand coding or by other tricks you can think of. Test each routine - you start with small field sizes and you can hand check that the code does what you expect.

If you get a chance, read the books "Hitch Hiker's Guide to the Galaxy". Rule number one is "Don't panic!". It's a good thing to remember smilie

Patience, persistence, truth,
Dr. mike
Jaya_21 (39) [Avatar] Offline
#61
Re: Sir . . Help please .!
Ur words are very encouraging.
Thanks , Sir. smilie

Sir,
I am now doing with the polynomial x^4 + x+ 1 with the curve equation
y^2 + xy = x^3 + g^4 +1 (a=g^4 , b=1).

I got the equation parameters a and b when I was referring to some paper.
When I need to move to higher order polynomials, what should I do Sir ?

From where wil I get the polynomial and curve parameters when I move to fields of higher size ?
drmike (543) [Avatar] Offline
#62
Re: Sir . . Help please .!
That equation should be:

y^2 + xy = x^3 + g^4*x^2 +1 (a=g^4 , b=1). And since g^4 = g+1 you can also write it as

y^2 + xy = x^3 + (g+1)*x^2 +1.

You can do a web search and see what other people have used, or you can use several different programs available on the net which will count points on curves for you. Look at PARI/GP and read about how other people have used it. The NIST curves are good too, but may not fit the size you need.
Jaya_21 (39) [Avatar] Offline
#63
Re: Sir . . Help please .!
Sir,

What size may fit an 8 bit processor , Sir?
U pls suggest some curves and polynomials for me.
My net search was not fruitful. smilie
drmike (543) [Avatar] Offline
#64
Re: Sir . . Help please .!
Check out the Certicom challenge curves here:
http://www.certicom.com/index.php/curves-list/1-software-security-providers/439-curves-list

The meaning of the data is explained in this paper:

http://www.certicom.com/images/pdfs/cert_ecc_challenge.pdf

I would try ECC2-79. It has been cracked, but it will be a great place to start!
Jaya_21 (39) [Avatar] Offline
#65
Re: Sir . . Help please .!
Thank U , Sir.

I had a look @ the curves.

Sir , As of today , I had implemented the ECDSA algorithm for the field 2^8 on a 8 bit proceesor. As I had told before , I had used the generator notations to do them. So , in my code I stored generator power as well as the binary string. For ex , if g^12 =1111 , I stored 12 as well as (1111).

Now I need to move to higjer fields. Say , ECC 79 as U say, I need to store the generator power which itself is very big and the integers. I dont think it wil b possible to do it on a 8 bit processor , Sir.

So I feel I should drop the thought of moving with generator notation. I donno how else to do.

All these days , U had been helping me lik anything and Sir , thanks is too small a word for ur support.

Pls help me now also Sir. Without generator notations , how can I proceed Sir ?
Pls work out the steps 4 d method U suggest 4 me for the following polynomial Sir.

x^4 + x + 1 ( a= g^4 , b =1)

Thaks a lot Sir.
drmike (543) [Avatar] Offline
#66
Re: Sir . . Help please .!
Think about look up tables. You can store the results of a^j where a is 1, 10, 11, 100, 101, ... The advantage of GF(2^m) is that all the cross terms of a multiply cancel out. So (a+b)^2 = a^2 + b^2. So you only have to store 79 terms for the squares of each possible bit. To compute the general power of a^m, you break up a into each coefficient and take those as a_k^m. Break up m as m=2*(s) or m = 2*(s+1), and drill down for each term of s.
In other words - you will figure out how to double and add every term. The computation will consist of doing a lookup for the powers of all the coefficients, xoring them together and getting a final result. You will need enough ram to hold two values, an intermediate result and a temporary result. The lookup table value will be the third value that is always added.

This is very easy to do, but hard to understand. I suggest doing it by hand with a small table of values so you get the idea. It will be slow, but it will work.

Along the way you might think of other ways to do things, so starting by hand is a great way to build understanding.
Jaya_21 (39) [Avatar] Offline
#67
Re: Sir . . Help please .!
Sir . .

In ur code , u had initialised a lot of polynomials.
What are the corresponding a and b values for those polynomials , Sir ?

How do I basicaaly know the equation parameters , given the field polynomial.

Can U pls give me polynomials of some lower order like 8,16 along with the a and b coefficients ?

Web sites give polynomials of high order only. smilie

Please Sir.
drmike (543) [Avatar] Offline
#68
Re: Sir . . Help please .!
The curve coefficients can be anything. I typically use random values for testing, but choose curves picked by mathematicians for real security. For your project, random values are fine. You can count the number of points on the curve by brute force - just check if any of the x values possible are on the curve and keep track of all the ones that are. For 8 or 16 bits this will take milliseconds, for 32 bits it will take a few minutes.

For 8 bit polynomials, you can choose many values for a and b, then count the number of points for each value chosen. Once you have a program written to do that, it won't take too long to find a curve with a "large prime number" as a factor. In this case, the number may be close to 100 and that would be the best you can do.
Jaya_21 (39) [Avatar] Offline
#69
Re: Sir . . Help please .!
Sir ,

1 .

In case of prime fields , when ve choose the coefficients , we check for conditions such as
4a^3 + 27b^2 (not equals ) 0.

From ur reply , I understand there is nothing of that kind in case for binary fields.
I can just randomly choose a and b values , count number of points in each case , proceed with that a and b for which the number of points are greater.
Am I correct , Sir ?

And Sir, from where do I get the polynomial list ?
Suggest me polynomials of lower order , Sir.

2.

And one more doubt , Sir.
Pls check out the following paper.

http://www.scialert.net/qredirect.php?doi=itj.2006.204.229&linkid=pdf
Refer to the section : Finite field GF ( 2^m ) using Polynomial Basis Representation
Page No. 9

I had used the method described in the above paper to do ECC in binary fields Sir.
I had used generator notations in my program.
g^0 , g^1 , g^2 . . . g^15 ( corresponding to elements 0001 , 0010 , etc ). (In case of 2^4)

I had used these elements to generate points on the curve as ( g^0 , g^6) , etc , etc.
But when elements were generated 0000 was also considered as an element. 0000 is not equal to any generator power.

So my program does not generate any point on the curve wich involves 0000.
How do I achieve this, Sir ?

3.

Methods on proceeding ECC in binary fields without generator notations.
Please. . .
drmike (543) [Avatar] Offline
#70
Re: Sir . . Help please .!
There might be some condition, but I'm not aware of it. You can't have a 4 as a coefficient because that's zero mod 2. Definitely pick random values, especially for smaller fields and brute force test all possible points. You will find about half the x's won't be on the curve.

There is no point for x = 0. Usually, that is the "point at infinity". If you add P and -P you get the point at infinity - a point which can not be represented bu tis mathematically part of the curve. I usually test for the point at infinity to make the code complete - O + P = P and P - P = O, etc.

Think of translating integers into polynomials. So 4 = 100, 12 = 1100 etc. Just count up from 1 to 2^n-1 and use that as an x value in your formula. You don't care where it is in the generator sequence - you just care if it is a point on the curve or not.

This is philosophically cheating - but who cares. It works! You will test every possible x value and find how many points are on each curve you try.
Jaya_21 (39) [Avatar] Offline
#71
Re: Sir . . Help please .!
Thank U , Sir.

Sir ,I hope U remember my project.
ECDSA - Sign Generation on 8 bit MCU ( substitute circuitry of Smart Card)
I have my project review tomorrow Sir.
During my last review , the question posted to me was the foll , Sir.

" When U say U are going to generate Signature on the Smart Card , fine. But what will the time complexity of running ur algorithm on the card ?
In case U will take 1 hour to generate the signature on card , there will be no use. "

I said I wil give it a thought.

I really didnt kno what the time complexity would be ?
They asked me to come out with papers which spk about this time complexity and prove that the sign wil be generated in a considerable time on the smart card.

Pls help me Sir.

How should I face this question ? smilie
drmike (543) [Avatar] Offline
#72
Re: Sir . . Help please .!
Some of the papers I suggested earlier talk about that. Look up Christof Paar:
http://www.crypto.ruhr-uni-bochum.de/en_paar.html and see what he says.

Doing DSA on an 8 bit micro will take a while, but it will be in the seconds range. When I wrote my book I was hopeful that 300MHz processors would soon come and make the time be less than 100 milliseconds. Today, we have 3 GHz processors, and 100MHz 8 bit micros in a smart card do exist. Read what Paar has to say about it on FPGA's, I'm sure it will translate into number of clock cycles which you can estimate on an 8 bit micro controller.

Seconds yes, maybe 10 seconds on a 20 MIPS processor. But if you can estimate the time it takes to do a single multiple in terms of clock cycles, you can more directly answer the question. How many clocks does it take to do an add? How many add's to a multiply? Work out the numbers and you can get an order of magnitude estimate. If it's less than 20 million cycles over all, then a 20 MIPS processor can do it in one second. A 100 MHz processor can do it in 1/5 second. If you can look at the disassembled code, you can count instructions and that will give you an estimate of clock cycles. For order of magnitude it is close enough.

Good luck on your exam!

Patience, persistence, truth,
Dr. mike