## Implementing ElGamal Elliptic Curve Cryptography

Steps of implementing ElGamal ECC:

1. Generating elliptic curve and choosing random base point ( $B$ )
2. Generating private and public key for the receiver ( A computes $P_A=k_AB$ and send it to B. B computes $P_B=k_BB$ )
3. Generating message and a random point ( message point = $P_m$, A then choose a random bit pattern $r$ )
4. Embed the message onto the curve and send the result with the random point ( A computes two points: $P_r=rB$ and $P_h=P_m+rP_B$ then send the two points to B)
5. Decrypt the ciphertext and make sure the data sent and received are the same ( B computes $P_s=k_BP_r$ and substracts this from $P_h$ to get $P_m=P_h-P_s$)

• #### Bobby Prabowo 12:42 pm on May 12, 2010 Permalink | Reply

kok eneg yah liatnya. wkwkwkw

• #### CG 2:00 pm on May 12, 2010 Permalink | Reply

keknya lebih eneg yang ngetik 😀

• #### CG 6:35 pm on October 4, 2011 Permalink | Reply

tft: eh kalem, yang udah advanced mah ga diposting disini, nanti disertasi gue dicuri orang 😛

## Implementing Diffie-Hellman Elliptic Curve Cryptosystem

The steps of simulating Diffie-Hellman key-exchange protocol are as follow:

1. Generating elliptic curve (Hard task. For cryptography we want the order of the curve to contain the largest prime number possible) and choosing a random base point on the chosen elliptic curve (let’s call the base point ‘B’)
2. Generating each sides private key (by generating random value)
3. Generating each sides public key (A computes $P_A=k_AB$  and B computes $P_B=k_BB$)
4. Show that each side gets the same shared secret ( $P_s = k_A(k_B) = k_B(k_A)$ )

[hey, do you notice that have successfully written the equations using latex? It’s fun and easy! Will post more difficult equations… ho ho ho… 😀 ]

## Setting up elliptic curve cryptosystems

Ufh, forgot to write this important things about setting up elliptic curve cryptosystems:

1. How many bits do I need?
2. How hard do I want to work?
3. How much time would it take to compute an elliptic curve secret key?
4. How to pick and choose elliptic curves?

These questions will be considered later, right now I will just make my codes work! 😀

## Developing Simple Protocols

After reading this book and getting more headaches while moving back and forth from chapter 5 to chapter 9, I decided to develop a code for two major protocols: Diffie-Hellman and ElGamal.

The earlier target was to observe the process of embedding a message into a point in elliptic curve, encrypt it, then decrypt it. The book provides the source code but I’m going to develop my own version to make it simpler and understandable, at least in my point of view 😉

Now I’m still configuring the data structure and trying to make the modules as simple as possible, using polynomial basis. I set the deadline to be at least next week!

• #### Rindu 11:01 am on June 27, 2008 Permalink | Reply

keep trying chika 🙂

## When is the best time to meet your advisor(s)?

If there is any of the so-called “best time”, ha ha ha

• #### soni 6:02 am on June 7, 2008 Permalink | Reply

sometimes i met my advisor on saturday! he is a workaholic, indeed!

ahhh, with those kind of advisor i guess you should’ve finished your study in 3 years or less… 😉

• #### Budi Rahardjo 6:08 pm on June 7, 2008 Permalink | Reply

What do you guys think? hi hi hi
[don’t talk behind my back. ha ha ha … ]

me and my phd fellow usually meet our advisor on fridays. and we usually manage to come up with sth to show 😉

• #### Rindu 11:40 am on June 8, 2008 Permalink | Reply

I will do it on the weekend …

• #### Rindu 10:26 am on June 10, 2008 Permalink | Reply

when we can meet chika?

@rindu: are you interested to be my advisor? 😀
if yes, will you only be available on weekends? hi hi hi…

• #### yuti 4:07 pm on June 13, 2008 Permalink | Reply

whoaoaa… dunia kecil, ternyata rekannya chika pemilik blog niatnulis.

@yuti: knapa yut? temennya temen saya yang jagoan kripto? 😀

• #### Rindu 1:06 am on June 14, 2008 Permalink | Reply

Belum ada new posting Chik ?

@rindu: wadaw! ada satu lagi “supervisor” yang tau aja kalau saya belum posting disini berarti tidak ada progres!!!
insya Allah segera ada posting mengenai progress, hasil bedrest kemarin ternyata malah baca buku lain2x yang tidak kripto, hi hi hi…
untuk yang tidak serius saya sering posting di sini

• #### yuti 10:34 pm on June 15, 2008 Permalink | Reply

iya, tahun lalu pas mas budi sulis baru bikin blog sering komen-komenan, dan ngga tahunya setahun kemudian kenal dengan chikara via blog juga… *dunia yang lucu XD*

## 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?

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.

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

## Implementing EC Cryptosystems

The core routines needed to implement EC cryptosystems are:

1. Choice of basis: polynomial or normal. Polynomial basis gives more speed but takes twice as much RAM, because multiplication doubles the number of bits stored before being reduced modulo the basis function. Normal basis uses minimal RAM but takes longer to compute, because the inversion routine is sometimes slower. A combination of both can work at best, but this makes things a bit more complicated.
2. Choice of curve: There are important cyptographic implications. But the ones with low order is avoided.

I’m working on polynomial coding now. Still focusing on curve operations. Hoping to finish it this week.

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r