## Setting up curves with different numbits for ElGamal

This book and the software is very useful for doing experiments of encrypting using elliptic curve cryptography. I’ve been reading some thread with questions on how to change curve parameters, and here’s how:

To change the number of bits, you have to set it in field2n.h

Choose the polynomial irreducible in polymain.c

Set the message to be encrypted in elgamal.c (important note: the length of the message depends on the numbits of the curve)

## Now reading

Mapping an Arbitrary Message to an Elliptic Curve when Defined over GF(2^n), Brian King, Indiana University – Purdue University Indianapolis 723 W Michigan, SL 160 Indianapolis, IN 46202International Journal of Network Security, Vol.8, No.2, PP.169–176, Mar. 2009.

• #### Johnb282 9:24 pm on May 28, 2014 Permalink | Reply

certainly like your website however you have to check the spelling on several of your posts. Many of them are rife with spelling problems and I to find it very troublesome to inform the truth nevertheless I will surely come back again. eafkedkbdegg

## Now reading

1. Implementation Aspects of Elliptic Curve Cryptography & An Introduction to Unified (Dual-Field) Arithmetic, Erkay Savas, Oregon State University (pdf)
2. Elliptic Curve Cryptosystems on Reconfigurable Hardware, Martin Christopher Rosner, Master Thesis, Worcester Polytechnic Institute, May 2008 (pdf)
3. Fast Algorithms for Elliptic Curve Cryptosystems over Binary Finite Field, [Published in K. Y. Lam and E. Okamoto, Eds., Advances in Cryptology – ASIACRYPT ’99, vol. 1716 of Lecture Notes in Computer Science, pp. 75–85, Springer-Verlag, 1999.], Yongfei Han, Peng-Chor Leong, Peng-Chong Tan, and Jiang Zhang (pdf)

## Reading list

1. Comparison of Galois Fields Multipliers in Standard and Composite Fields Architectures, Petrus Mursanto, Proceedings of National Conference on Computer Science and Information Technology 2007, January 29-30, 2007, Faculty of Computer Science, University of Indonesia.
2. A Scalable Dual-Field Elliptic Curve Cryptographic Processor, Akashi Satoh and Kohji Takano, IEEE TRANSACTIONS ON COMPUTERS, VOL. 52, NO. 4, APRIL 2003.
3. Eﬃcient Methods for Composite Field Arithmetic, E. Savas and C.  K. Koc, Technical Report, December 1999.
4. Implementation Options for Finite Field Arithmetic for Elliptic Curve Cryptosystems, Christof Paar, 1999.
5. Hardware Implementation of Eﬃcient Modiﬁed Karatsuba Multiplier Used in Elliptic Curves, Sameh M. Shohdy, Ashraf B. El-Sisi, and Nabil Ismail (Corresponding author: Sameh M. Shohdy), International Journal of Network Security, Vol.11, No.3, PP.138–145, Nov. 2010.
6. http://www.computer.org/portal/web/csdl/abs/html/trans/tc/2003/11/t1391.htm

## 4-bit curve

Now experimenting on a very small curve, taken from Guide to Elliptic Curve Cryptography #27, $F_2^4$ with reduction polynomial $f(z) = z^4+z+1$, $E: y^2 + xy = x^3 + z^3x^2 + (z^3+1)$ ($a = z^3$, $b = z^3+1$).

Have checked that the points on #81 are on curve.

Next to do is to perform curve operation $Q= k.P$

Notes:

This curve is not a Koblitz curve. Going compare this one with Koblitz (by changing a =1 or a = 0 and b = 1). To generate points on curve look at P1363.

• #### Budi Rahardjo 8:00 am on December 17, 2009 Permalink | Reply

Still thinking how to make a flexible ecc system to calculate all of these.

• #### CG 12:44 pm on December 17, 2009 Permalink | Reply

and what it’s gonna be called? a simulator? platform?

• #### soni 9:22 am on December 18, 2009 Permalink | Reply

what do you mean by ‘small curve’? if we only have 4 bit, it means that we only have a little bit combinations. then we have a rough curve, rather than a smooth curve if we have more bit. is it right?

• #### CG 4:55 pm on December 18, 2009 Permalink | Reply

@soni: i’m afraid it’s not that simple. yes that small curves will have only a small number of points but higher bits doesn’t not determine the smoothness of the curve. the curve is called “smooth” only if it is defined in real numbers, not in finite fields.

## My Research Analogy

I have posted some thoughts about my research to my less-strict and less-formal personality blogs here and here.

Enjoy 😉

• #### Milena 2:17 pm on December 7, 2008 Permalink | Reply

ph.d researcher? me,too:)
your blog linked to mine, this is how I found you.
http://www.phdcomics.com, have a look!
Milena
http://www.milenamoraru.wordpress.com

• #### mehobbes 3:12 am on December 8, 2008 Permalink | Reply

great idea!
how did you get this analogy?

## Curve generator

Have just downloaded a curve generator called ECB – Elliptic Curve Builder (and just found out that it’s executable for use under Win XP on 32-bit prosessors :(( ).

The important thing is to find out is whether the curves generated by ECB are secure, or not?

## Randomness and hiding information

The level of randomness is crucial for hiding information. The higher the level of randomness, the better. The design of cryptosystem is aiming at constructing crypto codes with “perfect avalanche” and good randomness.

Using optimal normal basis (or polynomial basis) math that looks like scrambled bits over an elliptic curve produce a fundamentally nonlinear output. A single bit change in the input will cause a nonlinear and very drastic change in the output.

Well, while symmetric crypto designers are working very hard on this, elliptic curves do it automatically 😉

• #### Tommi 9:11 am on June 4, 2008 Permalink | Reply

Do you mean chaos by randomness? That is, the possibility of a small change in initial conditions creating a large difference in the outcomes, even though every step of the process is deterministic.

Or is there actually a way to have true randomness in cryptography? I know next to nothing about it, so again please pardon the stupid questions.

• #### dwie 6:33 pm on June 4, 2008 Permalink | Reply

We say a sequence of numbers or bits is random if there is no causal relationship or corellations between any pair of numbers or bits in the sequence.

Chaos dynamic has the ability to produce random-like sequence, even though every step of the process is deterministic (as tommi said), and because of that, there is always correlation between any pair of numbers or bits which is produced by chaos dynamics.

Most crypto systems we used today are deterministic system so they cannot produce truly random sequence. They can only produce pseudorandom sequence.

“A single bit change in the input will cause a nonlinear and very drastic change in the output” is only a necessary condition for a system to produce sequence with good random-like-property.

• #### Tommi 1:53 pm on June 5, 2008 Permalink | Reply

So, a sequence is random if there is no way to compress it into shorter form? So, 232323232323…23 is not very random, because it is possible to just say “repeat 23” n times. Is this similar to the definition you are using?

• #### chikaradirghsa 11:34 am on June 6, 2008 Permalink | Reply

the randomness that i’m referring here is more about the process of generating the sequences, not about the pattern contained in the sequence.

or did i get the wrong idea? 😀

• #### budi sulis 4:10 pm on June 6, 2008 Permalink | Reply

@ chika,
I agree. The term random apply to a sequence only when we use the crypto system to generate the sequence.

If we refer to the processs: A good cryptosystem is just like a random permutation which maps an input which belong to a set to an output which belong to the same set.

• #### Tommi 11:36 pm on June 6, 2008 Permalink | Reply

Checking to see if I got it right this time: The point of randomness is to make it hard to see how close a guess was; if the function would be, say, continuous, it would be fairly easy to see if a guess is close to the actual input, but with a near-random system it is pretty hard.

• #### chikaradirghsa 6:16 pm on June 8, 2008 Permalink | Reply

Tommi: yes, you get it right. a near-random system makes it harder to make a guess based on “how close” the input to the output produced

## Converting text to point in ECC

I’m now building some simple codes for converting plain text character to a point on an elliptic curve.

Here’s how I’m gonna do it, based on Mike Rosing’s hints:

1. Take the data, and treat it as an x value
2. If x value fit on the curve, then find y. Each x value has two y values associated with it.
3. If x value does not fit on the curve, add extra bits to the data (but make sure not to mess with the raw data)
4. Check again
5. Repeat until the combination of the raw data and extra bits does fit on the curve.

To get the x value back, just mask off the extra bits to recover the raw data.

## ECC and diffusion?

After spending hours googling and reading some pdf and presentation files, I still cannot find the correlation between the term “diffusion” with ECC.

For now I do really think that the term “diffusion” is only for symmetric-key system.

Will find out more about it later. Hmmm….

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel