need help in elgamal's encryption

[mrjillberth]

I am going to do my first Java Project the ElGamal's Encryption.
Honestly, i have no idea yet on how to start my program because i don't have idea in encryption but i have to do it. Because it was assigned to me by our instructor. Please help me.

[NormR1]

Do you have the algorithm so you can design the code?
Is the program going to have a GUI or will its interface be via the commandline or console?
Do you have any specific questions?

[mrjillberth]

Honestly, i still don't have the algorithm but i am still looking for it although I already read some. It's just like this.
By the way, that could be a simple GUI just a TextField and a Button.
Algorithm:

Public parameters: q is a prime
p = 2kq+1 is a prime
g generator of Gp
Secret key of a user: x (where 0 < x < q)
Public key of this user: y = gx mod p
Message (or “plaintext”) : m

Encryption technique (to encrypt m using y)

1. Pick a number k randomly from [0…q-1]
2. Compute a = yk. m mod p . b = gk mod p
3. Output (a,b)

Honestly, I found it hard to understand in just reading this. That nobody is there to communicate with me. Please help me.

[NormR1]

In your posted algorithm there are still a lot of undefined terms.

p = 2kq+1 is a prime

What is k?

g generator of Gp

what does this mean?

[mrjillberth]

By the way, k is a random number to pick.
p = 2^k q + 1. and that is a prime.
g generator of Gp, honestly sir, i don't understand what's it. Maybe i still have to search more on that. So i can make it.
Do you have knowledge in cryptography sir? Especially in ElGamal. Can i have an explanation?

[NormR1]

I have no knowledge of the algorithm. I'm only a programmer, not a mathematician.

[Taywin]

To do this encryption, you have to break it into 3 parts - key generation, encryption, and decryption. You need to read how to generate a set of group which satisfies the rules. Please read about it at http://en.wikipedia.org/wiki/Generating_set_of_a_group to understand what it is. Read about elgamal encryption at http://en.wikipedia.org/wiki/ElGamal_encryption. Not too difficult but you need to understand symbols. It is similar to PKI stuff.

I believe this is one of your CS class. I thought your professor would have discussed about basic concept of this encryption algorithm?

[mrjillberth]

No, she only gave this to us because she said we can just search for it in the internet. She didn't gave any concept in crytography. I really wondered why she gave this to me.

[mrjillberth]

Anyway thanks for the help. If you can give me just a little overview about cryptography it would be highly appreciated by me.

[Taywin]

If you have no idea at all about cryptography, it is difficult to explain... You need to read more. One book may fit to your understanding than the other. Here are 2 links about Elgamal encryption.

http://ece.wpi.edu/~selcuk/ee578/chapter11.pdf
http://www.usna.edu/Users/math/wdj/book/node48.html

In plain word, a recipient must generate a public key using his or her own private key (in this case is a prime number). Then give the public key to any sender. A sender would encrypt the message (string) using the given public key value in the computation. The recipient will then be able to decrypt the message using another computation set and his or her private key.

Each cryptographic method has its own way to do. Though, many are very similar. Just take time to try to understand what it does. You could ignore the mathematical parts when you read it the first time even though the part is actually used to determine how well your encryption is. Hope these links would give you a bit more of the idea.

[sirlink99]

maybe try reading this http://en.wikipedia.org/wiki/ElGamal_encryption

What I know of encryption so far is that it uses matrices to hide the message. for example
[
[ = one large [

lets say your encryption matrix is
[1 2] [a b]
[3 4] [c d]

your decryption matrix would be

1r(ad-bc) [d -b]
----------[-c a]

so if you use the encryption matrix to encrypt a message hi

you would need to arrange the message into a matrix

[h i]
[z z]

the 'z' is nothing. If you wanted you could use key codes and replace the 'z' with a -

then you want to convert the message into either key codes, or alphabet values

[8 9]
[26 26]

once you have that you will want to multiply it by the encryption matrix (think of it as a 2d array. multiply row 1 by column 1 ([1][1] * [1][1] + [1][2] * [2][1]) would be your first value)

[1 2] . [8 9]
[3 4] [26 26]

which would give you

[60 61]
[128 131]

That is your encrypted message. if you were to find out your original message you will need to find the inverse or the encryption matrix, and then multiply the decryption matrix * encrypted message to get your original message back.

This is a simple encryption, but finding the inverse of a 3x3 matrix is much harder. This is the way I will try to encrypt. The other way is to think of a random algorithm to multiply each of the values with, and then just multiply it by the inverse of the algorithm to get the original value back.

I have no idea why I wrote this tutorial, but it seems to me that it is useful knowledge for a programmer to know, so I hope helps with some information for cryptography.

[mrjillberth]

Is it okay to encrypt a String with letters? How come! Mathematical expressions can only generate numbers and variables.
I already read some articles about ElGamal cryptography. But i really found it hard to easily understand all. Because I have nothing to communicate with and ask for explanation.

[sirlink99]

I am sure if you made a chart that just replaces letters with other ones you would do something like that.

lets say again that you message was hello if you swapped the letters like this

h = z
e = t
l = m
o = q

your message would look like
xtmmq

if you do not have the chart then it would be difficult to decode the message, but not impossible. It would make it easier if you had more words, because then you could reference the letters with other ones for example if you had a message like

m fmsn ntaskgvpwq

you would know that the m = a or an i because those are the only single letters that are used in a sentence

so you would know this
i fisn ntaskgvpq
or
a fasn ntaskgvpq

then you would know that n needs to be the same for both. As you can tell the more words you have the more references you have and the easier it is to decrypt the message. This is why numbers are used.

and lets say you tried multiplying the matrix example that I gave

encryption matrix
[a g]
[x q]

and your message was hi

[a g] . [h i]
[x q] [z z]

your new matrix would be

[ah+gz ai+gz]
[xh+qz xi+qz]

it would look like that. now if you see what is in common for the rows
first row has in common an 'a' and a 'g'. The second row has in common and x and an 'x' a 'q' and a 'z', since 'z' also appears in the top portion of the matrix we can assume that 'z' is in the lower half of the matrix. Then we divide each of the terms by what in the list of the common letters ('a','g','x','q') is in the term. Then we get the original message back

[h i]
[z z]

even if your message had an 'a' in it and you multiplied it by an a you would get a^2 and even if you divide by a you will get your a back. This is probably why they use letters, as you cannot reverse engineer the message without knowing the encryption matrix.

[mrjillberth]

Thanks Sir. It had been a great help for me. I'll be back if I have more questions.

[mrjillberth]

Encryption

package hahay;
import java.math.*;
import java.util.*;
import java.security.*;
import java.io.*;
public class ElGamal{
    public static void main(String[] args) throws IOException{
    	BufferedReader jill = new BufferedReader (new InputStreamReader (System.in));
        System.out.print("Enter the secret key: ");
        String sk = jill.readLine();
        System.out.print("Enter value of b: ");
        String pp = jill.readLine();
    	BigInteger p, b, c, secretKey;
        Random sc = new SecureRandom();
        secretKey = new BigInteger(sk);
        p = BigInteger.probablePrime(64, sc);
        b = new BigInteger(pp);
        c = b.modPow(secretKey, p);
        System.out.print("Enter your Big Number message: ");
        String s = jill.readLine();
        BigInteger X = new BigInteger(s);
        BigInteger r = new BigInteger(64, sc);
        BigInteger EC = X.multiply(c.modPow(r, p)).mod(p);
        BigInteger brmodp = b.modPow(r, p);
        System.out.println("p = " + p);
        System.out.println("secretKey = " + secretKey);
        System.out.println("EC = " + EC);
        System.out.println("b^r mod p = " + brmodp);

    }
}

Decryption

package hahay;
import java.math.*;
import java.util.*;
public class Decrption {
	public static void main (String[]yeah){
		Scanner jill = new Scanner (System.in);
		
		System.out.print("b^r mod p: ");
		String brmodpp = jill.next();
		BigInteger brmodp = new BigInteger(brmodpp);
		System.out.print("Enter the secret key: ");
		String sk = jill.next();
		BigInteger secretkey = new BigInteger(sk);
		System.out.print("Enter the value of p: ");
		String pp = jill.next();
		BigInteger p = new BigInteger(pp);
		System.out.print("Enter the value of EC: ");
		String ec = jill.next();
		BigInteger EC = new BigInteger(ec);
		
		BigInteger crmodp = brmodp.modPow(secretkey, p);
        BigInteger d = crmodp.modInverse(p);
        BigInteger ad = d.multiply(EC).mod(p);
        System.out.println("\n\nc^r mod p = " + crmodp);
        System.out.println("d = " + d);
        System.out.println("Alice decodes: " + ad);

	}
	
}

I can only generate numbers but not with letters. I don't know how to generate letters.

[Taywin]

For letters, you just iterate through a string and use each char value (supposedly ASCII value of a character for simplicity) as a number.

[mrjillberth]

Yes, thanks!
But i will mark it as solved as soon as my problem could be solved. But your help will contribute to my success. Thanks!