RSA algorithm(java)

[Pallavi Tumbigeremat]

package rsa;

/**
*
* @author Palllvi T M
*/
import java.util.Scanner;

public class Rsa {
   public static int mult (int x,int y,int n){
       int k=1;
       int j;
       for(j=1;j<=y;j++);
       k=(k=x)%n;
       return k;
   }
public static int gcd(int m,int n){
   if (n==0)
       return m;
   else
       return (gcd(n,m%n));  
}
    /**
    * @param args the command line arguments
    */
   public static void main(String[] args) {
       // TODO code application logic here
int msg, PlainText,CipherText;
int n,d=0,e,z,p,q,i;
Scanner sc=new Scanner(System.in);
System.out.print("enter the values of primes p and q");
p=sc.nextInt();
q=sc.nextInt();
System.out.print("enter msg such that(msg is less than or equal to(p*q)-z");
msg=sc.nextInt();
n=p*q;
z=(p-1)*(q-1);
do{
   System.out.print("choose the value of e(e>z) such that gcd(z,e)=1:");
   e=sc.nextInt();
}while(gcd(z,e)!=1);
       i=2;
       while(((i*e)%z)!=1)
       {
   i++;
   d=i;
}
System.out.println("the public key pair is("+e+","+n+")");
System.out.println("the public key pair is("+d+","+n+")");
CipherText=mult(msg,e,n);
System.out.println("CipherText="+CipherText);
PlainText=mult(CipherText,d,n);
System.out.println("PlainText="+PlainText);

}
   }
   



output:
enter the values of primes p and q5 7
enter msg such that(msg is less than or equal to(p*q)-z30
choose the value of e(e>z) such that gcd(z,e)=1:5
the public key pair is(5,35)
the public key pair is(5,35)
CipherText=30
PlainText=30

is the output correct???
if not please tell me the changes

[Matt Wong]

I didn't tried to read your stuff as
1) it doesn't use code tags
2) uses 32-bit ints
3) input is wrong as you re-use one of the primes

Wikipedia uses these values:

p = 61
q = 53

This gives N = p x q = 61 x 53 = 3233

EN.wiki uses Carmichael's totient function - I don't know this and instead use what Java uses and what is used on DE.wiki: Euler's totient function - wich is: phi(N) = (p-1) x (q-1) = (61 - 1) x (53 - 1) = 60 x 52 = 3120

Now you have to choose e - wich has to be co-prime to phi(N) - this where you made your mistake and re-used p - NO! - you have to use something else! In real security a common used value is 65537 - wich is 2^16+1 - 4th Fermat number. Wiki choosen e = 17.

So, public key is (N,e) = (3233,17)

Now, you have to calculate d - and this is where standard API comes in - java.math.BigInteger offers the method modInverse() wich is also used in SUNs RSA implementation - wich in this case gives you d = 413.

So, private key is (N,d) = (3233,413)

Then the RSA-"magic" is : m^e mod N - where m is the message - your code shows two errors:

for(j=1;j<=y;j++); <br /> <br /> Dang - loop without body. <br /> <br /> k=(k=x)%n; <br /> <br /> I doubt this is valid java code. Also, whatever this is meant to do - it's not what you think. Again, this is where standard API offers (and is used) : BigInteger.modPow(). <br /> <br /> To sum it up: <br />

BigInteger p=BigInteger.probablePrime(2048, SecureRandom.getInstance("SHA1PRNG")), q, N;
do
{
	q=BigInteger.probablePrime(2048, SecureRandom.getInstance("SHA1PRNG"));
	N=p.multiply(q);
} while(N.bitLength()!=4096);
BigInteger phiN=p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
BigInteger e=BigInteger.valueOf(65537L);
BigInteger d=e.modInverse(phiN);

<br /> <br /> According to grepcode - this is real java code: <br />

    // generate the keypair. See JCA doc
    public KeyPair generateKeyPair() {
        // accommodate odd key sizes in case anybody wants to use them
        int lp = (keySize + 1) >> 1;
        int lq = keySize - lp;
        if (random == null) {
            random = JCAUtil.getSecureRandom();
        }
        BigInteger e = publicExponent;
        while (true) {
            // generate two random primes of size lp/lq
            BigInteger p = BigInteger.probablePrime(lp, random);
            BigInteger q, n;
            do {
                q = BigInteger.probablePrime(lq, random);
                // convention is for p > q
                if (p.compareTo(q) < 0) {
                    BigInteger tmp = p;
                    p = q;
                    q = tmp;
                }
                // modulus n = p * q
                n = p.multiply(q);
                // even with correctly sized p and q, there is a chance that
                // n will be one bit short. re-generate the smaller prime if so
            } while (n.bitLength() < keySize);

            // phi = (p - 1) * (q - 1) must be relative prime to e
            // otherwise RSA just won't work ;-)
            BigInteger p1 = p.subtract(BigInteger.ONE);
            BigInteger q1 = q.subtract(BigInteger.ONE);
            BigInteger phi = p1.multiply(q1);
            // generate new p and q until they work. typically
            // the first try will succeed when using F4
            if (e.gcd(phi).equals(BigInteger.ONE) == false) {
                continue;
            }

            // private exponent d is the inverse of e mod phi
            BigInteger d = e.modInverse(phi);

            // 1st prime exponent pe = d mod (p - 1)
            BigInteger pe = d.mod(p1);
            // 2nd prime exponent qe = d mod (q - 1)
            BigInteger qe = d.mod(q1);

            // crt coefficient coeff is the inverse of q mod p
            BigInteger coeff = q.modInverse(p);

            try {
                PublicKey publicKey = new RSAPublicKeyImpl(n, e);
                PrivateKey privateKey =
                        new RSAPrivateCrtKeyImpl(n, e, d, p, q, pe, qe, coeff);
                return new KeyPair(publicKey, privateKey);
            } catch (InvalidKeyException exc) {
                // invalid key exception only thrown for keys < 512 bit,
                // will not happen here
                throw new RuntimeException(exc);
            }
        }
    }

<br /> <br /> So, it's easy to spot that something is wrong with what you tried, as 30^5 mode 35 cleary isn't 30 - but 25. <br /> <br /> Advice: don't try to write your own security - use what Java already provides and what's common: create random AES key - wrap with RSA and use AES for message encryption - this looks - warning: bad code incoming - something like this: <br /> <br />

KeyPairGenerator keyPairGenerator=KeyPairGenerator.getInstance("RSA");
keyPairGenerator.initalize(new RSAKeyGenParameterSpec(4096, RSAKeyGenParameterSpec.F4), SecureRandom.getInstanceStrong());
KeyPair keyPair=keyPairGenerator.generateKeyPair();

byte[] rsaPublic=keyPair.getPublic().getEncoded();

-> send byte[] rsaPublic to other side

<br />

-> from other side: byte[] rsaPublic

KeyFactory keyFactory=KeyFactory.getInstance("RSA");
PublicKey publicKey=keyFactory.generatePublic(new X509EncodedKeySpec(rsaPublic));

KeyGenerator keyGenerator=KeyGenerator.getInstance("AES");
keyGenerator.init(256, SecureRandom.getInstanceStrong());
SecretKey secretKey=keyGenerator.generateKey();

Cipher keyEncryptor=Cipher.getInstance("RSA/ECB/OAEPWithSHA-256AndMGF1Padding");
keyEncryptor.init(Cipher.WRAP_MODE, publicKey);
byte[] encryptedAESKey=keyEncryptor.wrap(secretKey);

-> send byte[] encryptedAESKey to other side

Cipher dataEncryptor=Cipher.getInsatnce("AES/OFB/NoPadding");
dataEncryptor.init(Cipher.ENCRYPT_MODE, secretKey, SecureRandom.getInstanceStrong());
byte[] initVector=dataEncryptor.getIV();

-> send byte[] initVector to other side (doesn't need to be secret as long as any pair of secretKey and initVector are never re-used)

byte[] encryptedData=dataEncryptor.doFinal(data);

-> send byte[] encryptedData to other side

-> from other side: byte[] encryptedAESKey
-> from other side: byte[] initVector
-> from other side: byte[] encryptedData

Cipher keyDecryptor=Cipher.getInsatnce("RSA/ECB/OAEPWithSHA-256AndMGF1Padding");
keyDecryptor.init(Cipher.UNWRAP_MODE, keyPair.getPrivate);
Key secretKey=keyDecryptor.unwrap(encryptedAESKey, "AES", Cipher.SECRET_KEY);

Cipher dataDecryptor=Cipher.getInstance("AES/OFB/NoPadding");
dataDecryptor.init(Cipher.DECRYPT_MODE, secretKey, new IvParamterSpec(initVector));
byte[] decryptedData=dataDecryptor.doFinal(encryptedData);

But what you really should use is TLS. Hint: for generating certificate either use OpenSSL if you have access to linux - otherwise you can get a PKI up with bouncycastle. But that's a topic for another thread.

[Campbell Ritchie]

Pallavi Tumbigeremat wrote:.  . .
       for(j=1;j<=y;j++);
       k=(k=x)%n;
. . .

Code tags or no code tags, please explain those two lines.

Too difficult a question for its current location: moving to our security forum.

[Matt Wong]

so - first of all - I cleaned up your code - re-formatted it - and, most important of all - put it into code-tags:

package rsa;
/**
*
* @author Palllvi T M
*/
import java.util.Scanner;
public class Rsa
{
	public static int mult (int x,int y,int n)
	{
		int k=1;
		int j;
		for(j=1;j<=y;j++);
		k=(k=x)%n;
		return k;
	}

	public static int gcd(int m,int n)
	{
		if (n==0)
			return m;
		else
			return (gcd(n,m%n));
	}

	/**
	* @param args the command line arguments
	*/
	public static void main(String[] args)
	{
		// TODO code application logic here

		int msg, PlainText,CipherText;
		int n,d=0,e,z,p,q,i;

		Scanner sc=new Scanner(System.in);

		System.out.print("enter the values of primes p and q");
		p=sc.nextInt();
		q=sc.nextInt();

		System.out.print("enter msg such that(msg is less than or equal to(p*q)-z");
		msg=sc.nextInt();

		n=p*q;
		z=(p-1)*(q-1);

		do
		{
			System.out.print("choose the value of e(e>z) such that gcd(z,e)=1:");
			e=sc.nextInt();
		}while(gcd(z,e)!=1);

		i=2;

		while(((i*e)%z)!=1)
		{
			i++;
			d=i;
		}

		System.out.println("the public key pair is("+e+","+n+")");
		System.out.println("the public key pair is("+d+","+n+")");

		CipherText=mult(msg,e,n);
		System.out.println("CipherText="+CipherText);
		PlainText=mult(CipherText,d,n);
		System.out.println("PlainText="+PlainText);
	}
}

so - now lets try to split up what you tried - what you did - and what went wrong

Line 33/34

		int msg, PlainText,CipherText;
		int n,d=0,e,z,p,q,i;

yes - it's "legal" java code - but - conventions states, that each variable is written in its own line - so it should look like this:

		int msg;
		int PlainText;
		int CipherText;
		int n;
		int d=0;
		int e;
		int z;
		int p;
		int q;
		int i;

next logic issue: primitives always set to thier defaults - for int default is 0 - but - it makes a difference if you just declare a reference - or if you correctly initialize it
also - convention: variables use "lowerCamelCase"
to pretty it up - that's what it should look like:

		int msg=0;
		int plainText=0;
		int cipherText=0;
		int n=0;
		int d=0;
		int e=0;
		int z=0;
		int p=0;
		int q=0;
		int i=0;

next we got at line 36 - Scanner-mess

		Scanner sc=new Scanner(System.in);

		System.out.print("enter the values of primes p and q");
		p=sc.nextInt();
		q=sc.nextInt();

		System.out.print("enter msg such that(msg is less than or equal to(p*q)-z");
		msg=sc.nextInt();

Ok - you got it working - but I guess only by luck - you shouldn't try to read console input this way.
Here you have a more reliable one:

import java.io.*; // include InputStreamReader and BufferedReader
//...
BuffereReader bufferedReader=new BufferedReader(new InputStreamReader(System.in)); // should be done only once and saved to a singleton static
//...
String line=bufferedReader.readLine();
int someInt=Integer.parseInt(line);

So here is something a bit more common - so it's also way better recognized by experienced coders:

		BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));

		System.out.println("enter the values of primes");
		System.out.print("p=");
		p=Integer.parseInt(bufferedReader.readLine());
		System.out.print("q=");
		q=Integer.parseInt(bufferedReader.readLine());

		System.out.println("enter msg such that msg is less than or equal to (p*q)-z");
		msg=Integer.parseInt(bufferedReader.readLine());

I'm not quite sure about that "less than (p*q)-z" - but "equal to" is surely wrong as this would result in "0" - so it has to be "less than". Also - you're using Euler PHI function - so your "z" should named "phi" or "phiN":

		n=p*q;
		z=(p-1)*(q-1);

Just look at my code - or at SUNs code.

So you say your message should be "less than or equal" than: p x q - phiN
No parentheses need as basic math rule states: "multiply/divide always comes before addition/subtraction" - so writing "p x q - phiN" implies you also do "p x q" first - wich is N - and then do "N - phiN" as second step.
Also we now see - this is wrong. In RSA message has to be one bit shorter than modulus: for RSA2048 with N.length 2048 message can up to 2047 bits - as we use 8 bit per byte in modern computers - next lowest value would be 2040bits - this is clearly bigger than "N - phiN". Remember: phiN is (p-1) x (q-1), so you would end up with limit of:

p x q - (p-1)x(q-1)

Simple not-so-real-world-example with some big primes:

p=63709
q=48487

We ignore that it should be: p < q - for this example. <br /> <br /> N=3089058283 <br /> phiN=(63709-1)x(48487-1)=63708x48486=3088946088 <br /> <br /> So with your limit you would end up with just 112195 - wich is just 17 bits - but you could go up to 31 bits - wich would be 2147483647 - when bound to 8bit-per-byte - we would end up with 24bits wich would be 16777215. <br /> <br /> Next: line 48 <br />

		do
		{
			System.out.print("choose the value of e(e>z) such that gcd(z,e)=1:");
			e=sc.nextInt();
		}while(gcd(z,e)!=1);

Ok - text says what you try to get here - a random number co-prime to phiN. At least you're doin the right thing wich I didn't - you checked for co-prime.
Why is co-prime important? If you get a non-co-prime you end up with a multiple of phiN wich ends up in "0" after modulus.

Line 54

		i=2;

		while(((i*e)%z)!=1)
		{
			i++;
			d=i;
		}

Not sure about that - about it looks like modInverse to calculate d. This is already in Java: BigInteger.modInverse().

Last line: 9

	public static int mult (int x,int y,int n)
	{
		int k=1;
		int j;
		for(j=1;j<=y;j++);
		k=(k=x)%n;
		return k;
	}

I didn't even tried to understand what you tried to do here - but "for();" is just an empty loop after wich you do nothin with your counter so you end up with just return x%n - wich obviously isn't the RSA "magic" function: msg^e mod N.


So, after going through your code one can easy spot some issues wich clearly breaks what ever you tried to accomplish.
This is why you should not try to implement your own crypto - and as you seen - I missed check for co-prime - so even I'm really into this stuff - I also made a huge mistake wich could end up in just "0" by getting unlucky with primes. Even the bit I posted below wich at least tries to go for somewhat like anonymous RSA with AES - it's garbage and shouldn't used even for local file encryption.

If you want I could go for way more secure way using BouncyCastle wich provides secure ways to generate and handle local file encryption. For network connections you should go with TLS - wich Java always brings along and needed certificates can easy generated with openssl or with BouncyCastle.