[Ghoser777]

I was hoping to show my class some sample code I had written in java demonstrating how public private key encryption works. I thought I got the mathematics implemented correctly (it actually does work sometimes), but something seems to be missing. Can anyone spot what's wrong with my algorithm?

Code:
import java.math.*;
import java.util.*;

public class CryptoInfo
{
	private BigInteger n; //public mod
	private BigInteger e; //public key
	private BigInteger d; //private key
	
	public static void main(String[] args)
	{
		String message = "Hello World!";
		
		CryptoInfo me = new CryptoInfo(new BigInteger("5"), new BigInteger("19"));
		CryptoInfo you = new CryptoInfo(new BigInteger("23"), new BigInteger("29"));
		
		String encryptMess = me.prepareSignedMessage(message, 
				                             you.getPublicEncryptionKey(),
				                        you.getPublicModulus());
													 
		System.out.println(encryptMess);
		
		String decryptMess = you.readSignedMessage(encryptMess, 
		      me.getPublicEncryptionKey(),
		      me.getPublicModulus());
													 
		System.out.println(decryptMess);
	}
	
	//should make sure p and q are valid primes
	public CryptoInfo(BigInteger p, BigInteger q)
	{
		n = p.multiply(q);
		
		//phi(n) equals this only because p and q are distinct primes
		BigInteger phiN = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
		
		e = randomEncryptionKey(phiN);
		d = e.modInverse(phiN);
	}
	
	public BigInteger getPublicEncryptionKey()
	{
		return e;
	}
	
	public BigInteger getPublicModulus()
	{
		return n;
	}
	
	//prepares a signed, encrypted message for the user with passed in public key and public mod
	public String prepareSignedMessage(String message, BigInteger otherKey, BigInteger otherMod)
	{
		BigInteger[] big = encrypt(bigIntsForMessage(message), d, n); //encode using our private key
		big = encrypt(big, otherKey, otherMod); //encode using their public key
		
		return stringRepForBigInts(big);
	}
	
	//decodes a signed message from the user with the passed in public key and public mod
	public String readSignedMessage(String encryptedMessage, BigInteger otherKey, BigInteger otherMod)
	{
		BigInteger[] big = encrypt(bigIntsForStringRep(encryptedMessage), d, n); //decode our using private key
		big = encrypt(big, otherKey, otherMod); //decode using their public key
		
		System.out.println(stringRepForBigInts(big));
		
		return messageForBigInts(big);
	}
	
	//returns a BigInteger g between 2 and phiN-1 such that
	//g and phiN are relatively prime
	private BigInteger randomEncryptionKey(BigInteger phiN)
	{
		BigDecimal r;
		BigInteger g;
		
		BigDecimal decPhi = new BigDecimal(phiN);
		
		do
		{
			r = new BigDecimal(Math.random());
			r = r.multiply(decPhi);
			g = r.toBigInteger();
		}
		while(g.compareTo(BigInteger.ONE) <= 0 || !g.gcd(phiN).equals(BigInteger.ONE));
		//do this whil g is less than or equal to 1 or g is not relatively prime to phiN
		
		return g;
	}
	
	
	//encrypts an array of BigInteger values using the passed in key and modulus
	public BigInteger[] encrypt(BigInteger[] code, BigInteger key, BigInteger mod)
	{
		BigInteger[] array = new BigInteger[code.length];
		for(int i=0; i<code.length; i++)
			array[i] = encrypt(code[i], key, mod);
			
		return array;
	}
	
	//encrypts one BigInteger value using the passed in key and modulus
	public BigInteger encrypt(BigInteger val, BigInteger key, BigInteger mod)
	{
		BigInteger temp = BigInteger.ONE;
		for(BigInteger i = BigInteger.ZERO; i.compareTo(key) < 0; i = i.add(BigInteger.ONE))
			temp = temp.multiply(val).mod(mod);
			
		return temp;
	}
	
	
	//converts an array of BigIntegers to the appropriate English rep
	//i.e. not numbers delineated by commas, but actual ascii values
	//of the BigIntegers turned into chars
	public String messageForBigInts(BigInteger[] ascii)
	{	
		StringBuffer buff = new StringBuffer(ascii.length);
		for(int i = 0; i<ascii.length; i++)
			buff.append((char)ascii[i].intValue());
		return buff.toString();
	}
	
	//converts an array of BigIntegers to a comma delineated String of numbers
	public String stringRepForBigInts(BigInteger[] nums)
	{
		StringBuffer buff = new StringBuffer(nums.length);
		for(int i = 0; i<nums.length; i++)
		{
			buff.append(nums[i].toString());
			if(i != nums.length-1)
				buff.append(",");
		}
		return buff.toString();
	}
	
	//converts an english message to an array of big ints
	public BigInteger[] bigIntsForMessage(String message)
	{
		BigInteger[] array = new BigInteger[message.length()];
		for(int i=0; i<message.length(); i++)
			array[i] = new BigInteger((int)message.charAt(i) + "");
		return array;
	}
	
	//converts a comma-delineated string into appropraiet big ints
	public BigInteger[] bigIntsForStringRep(String rep)
	{
		StringTokenizer tokenizer = new StringTokenizer(rep,",");
		BigInteger[] array = new BigInteger[tokenizer.countTokens()];
		
		int i = 0;
		while(tokenizer.hasMoreTokens())
		{
			array[i] = new BigInteger(tokenizer.nextToken());
			i++;
		}
		
		return array;
	}
}

This code actually starts working, for no good reason from my point of view, if I make the "5" into a "17" when I'm creating my CryptoInfo object. I'm kind of at a lost.

Thanks,
Matt Fahrenbacher

[beamso]

Just so I understand what you're doing, you're signing the message before encrypting the message for the other party to decrypt.

I can't work out your encryption function, but try using BigInteger.modPow() rather the code you've got there ( I don't understand what it's doing).

This is just a pedantic thing, but try and encrypt single numbers rather than arrays of numbers.

[Ghoser777]

modPow gives me the exact same (wrong) answer - I was just calculating the modPow manually before. So strange...

Thanks,
Matt Fahrenbacher

[Ghoser777]

Okay... perhaps it's my random encrpytion key that is messed up? I think that method does what I want (e and phiN are relatively prime by the end), but it seems that based on which random encryption key is chosen, sometimes I get an encoding/decoding scheme that works, other times I don't.

Weird....

Matt Fahrenbacher

[Ghoser777]

Okay, I get what the problem is now... I just don't know a good fix for it.

If person A has public mod of 30 and person B has public mod of 21, then the scenario is something like this:

encrypt(M, key, 30) (value will be between 0 and 29)
encrypt(M, key, 21) (takes a value from 0 to 29 and converts it to a value from 0 to 20)
encrypt(M, key, 21) (takes a value from 0 to 20 and converts it to a value from 0 to 20)
encrypt(M, key, 30) (takes a value from 0 to 20 and converts it to a value from 0 to 29)

Now here's where things get ugly - the middle two operations are suppose to undo each other - so after them, we should be back to where we were after only on encrypt call. Unfortunately, if the first call to encrypt leaves us with an int between 21 and 29 (possible), then the next two calls of encrypt will not return us back to where we want to be. Instead we will end up with a value between 0 and 20... which is why I keep getting garbage after the final encrypt call.

Okay, now that I've isolated the problem (I hope), does anyone have an idea of how to solve it?

Thanks,
Matt Fahrenbacher

[Ghoser777]

Fixed! Well, the comments indicate that there still could be a potential bug everyone in a while, but it should be very very very rare.

Thanks everyone for letting me express my problem (look at the readSignedMessage method for the comments)!

Matt Fahrenbacher

Code:
import java.math.*;
import java.util.*;

public class CryptoInfo
{
	private BigInteger n; //public mod
	private BigInteger e; //public key
	private BigInteger d; //private key
	
	private Random r = new Random();
	
	public static void main(String[] args)
	{
		CryptoInfo me = new CryptoInfo();
		CryptoInfo you = new CryptoInfo();
	
		String message = "Is this working yet?!?!?!";
		
		BigInteger yourPublicKey = you.getPublicEncryptionKey();
		BigInteger yourPublicMod = you.getPublicModulus();
		
		BigInteger myPublicKey = me.getPublicEncryptionKey();
		BigInteger myPublicMod = me.getPublicModulus();
	
		String encryptMess = me.prepareSignedMessage(message, yourPublicKey, yourPublicMod);
												 
		String decryptMess = you.readSignedMessage(encryptMess, myPublicKey, myPublicMod);
		
		System.out.println(decryptMess);
	}
	
	//Creates a CryptoInfo instance using primes of size 10 bits
	public CryptoInfo()
	{
		this(10);
	}
	
	//Creates a CryptoInfo instance using primes with the indicated total number of bits
	public CryptoInfo(int bits)
	{
		if(bits <= 6)
			throw new IllegalArgumentException("Bits must exceed 6");
	
		BigInteger nth, mth; //need nth and mth to be distinct numbers so we're not picking p and w to be the same prime
		//nth and mth refer to which prime we're considering, so we want to at least pick a prime that is three digits long
		//so we need to pick a number that is at least the 26th prime
				
		do
			nth = new BigInteger(bits, r);
		while(nth.compareTo(new BigInteger("26"))<0);
		
		do
			mth = new BigInteger(bits, r);
		while(mth.compareTo(new BigInteger("26"))<0 || mth.equals(nth));
		
		initialize(nthPrime(nth),nthPrime(mth));
	}
	
	//creates a CryptoInfo instance using the indicated two primes
	public CryptoInfo(BigInteger p, BigInteger q)
	{
		initialize(p,q);
	}
	
	//private helper method needed because you can only call other constructors
	//on the first line of a constructor
	private void initialize(BigInteger p, BigInteger q)
	{
		if(!isPrime(p) || !isPrime(q))
			throw new IllegalArgumentException("Either p or q (or both) are not prime");
		else if(p.equals(q))
			throw new IllegalArgumentException("p and q are not distinct primes");
	
		n = p.multiply(q);
		
		//phi(n) equals this only because p and q are distinct primes
		BigInteger phiN = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
		
		System.out.println("P:" + p + "\nQ:" + q + "\nN:" + n + "\nphiN:" + phiN);
		
		e = randomEncryptionKey(phiN);
		d = e.modInverse(phiN);
	}
	
	//returns the public encryption key for the current CryptoInfo
	public BigInteger getPublicEncryptionKey()
	{
		return e;
	}
	
	//returns the public modulus for the current CryptoInfo
	public BigInteger getPublicModulus()
	{
		return n;
	}
	
	//returns the private encryption key for the current CryptoInfo
	private BigInteger getPrivateKey()
	{
		return d;
	}
	
	//prepares a signed, encrypted message for the user with passed in public key and public mod
	public String prepareSignedMessage(String message, BigInteger otherKey, BigInteger otherMod)
	{
		BigInteger[] big = encrypt(bigIntsForMessage(message), getPrivateKey(), getPublicModulus()); //encode using our private key
		big = encrypt(big, otherKey, otherMod); //encode using their public key
		
		return stringRepForBigInts(big);
	}
	
	//decodes a signed message from the user with the passed in public key and public mod
	public String readSignedMessage(String encryptedMessage, BigInteger otherKey, BigInteger otherMod)
	{
		BigInteger[] big = encrypt(bigIntsForStringRep(encryptedMessage), getPrivateKey(), getPublicModulus()); //decode using our private key
		BigInteger[] temp = encrypt(big, otherKey, otherMod); //decode using their public key
		
		//In the temp array, we might end up with values that make no sense because of this reason:
		//Let's say my public mod is 30 and yours is 21.
		//If when I encrypt using my private key I get a value between 22 and 29, then encrypting
		//with your public key and then with your private key will at most give me a value in the
		//range of 0 to 20.  But to correctly get back to where we were, we need to end up getting 
		//a value between 22 and 29 (which is impossible).  So to fix this, in the event that we
		//get a decrypted value that isn't a valud ascii value, we need to add to the pre-decrypted
		//value the proper modulus enough times tell after we decrypt, we get something useful.
		
		//i.e.
		//Say we encrypt the letter 'c' and we get 28 mod 30
		//Then when we encrypt and decrypt 28 mod 21, we get the number 7
		//But the middle stage of our encryption should just undo each
		//other and we should get 28 back.  So instead, we need to add
		//21 to our answer to get 28 back. (Because 28 % 21 == 7... so we
		//lost some info)
		
		//In theory, this could break in the event where we wrap around so many times
		//that we end up at a number between 0 and 127.  But this will (hopefully) be
		//rare for our uses.
		BigInteger max = new BigInteger("127");
		for(int i=0; i<temp.length; i++)
		{
			while(temp[i].compareTo(max) > 0) //descending, tempInt is bigger than max
			{
				big[i] = big[i].add(getPublicModulus());
				temp[i] = encrypt(big[i], otherKey, otherMod);
			}
		}
		
		return messageForBigInts(temp);
	}
	
	//returns a BigInteger g between 2 and phiN-1 such that
	//g and phiN are relatively prime
	private BigInteger randomEncryptionKey(BigInteger phiN)
	{
		BigDecimal r;
		BigInteger g;
		
		BigDecimal decPhi = new BigDecimal(phiN);
		
		do
		{
			r = new BigDecimal(Math.random());
			r = r.multiply(decPhi);
			g = r.toBigInteger();
		}
		while(g.compareTo(BigInteger.ONE) <= 0 || !g.gcd(phiN).equals(BigInteger.ONE));
		//do this whil g is less than or equal to 1 or g is not relatively prime to phiN
		
		return g;
	}
	
	
	//encrypts an array of BigInteger values using the passed in key and modulus
	public BigInteger[] encrypt(BigInteger[] code, BigInteger key, BigInteger mod)
	{
		BigInteger[] array = new BigInteger[code.length];
		for(int i=0; i<code.length; i++)
			array[i] = encrypt(code[i], key, mod);
			
		return array;
	}
	
	//encrypts one BigInteger value using the passed in key and modulus
	public BigInteger encrypt(BigInteger val, BigInteger key, BigInteger mod)
	{
		return val.modPow(key,mod);
	}
	
	
	//converts an array of BigIntegers to the appropriate English rep
	//i.e. not numbers delineated by commas, but actual ascii values
	//of the BigIntegers turned into chars
	public String messageForBigInts(BigInteger[] ascii)
	{	
		StringBuffer buff = new StringBuffer(ascii.length);
		for(int i = 0; i<ascii.length; i++)
			buff.append((char)ascii[i].intValue());
		return buff.toString();
	}
	
	//converts an array of BigIntegers to a comma delineated String of numbers
	public String stringRepForBigInts(BigInteger[] nums)
	{
		StringBuffer buff = new StringBuffer(nums.length);
		for(int i = 0; i<nums.length; i++)
		{
			buff.append(nums[i].toString());
			if(i != nums.length-1)
				buff.append(",");
		}
		return buff.toString();
	}
	
	//converts an english message to an array of big ints
	public BigInteger[] bigIntsForMessage(String message)
	{
		BigInteger[] array = new BigInteger[message.length()];
		for(int i=0; i<message.length(); i++)
			array[i] = new BigInteger((int)message.charAt(i) + "");
		return array;
	}
	
	//converts a comma-delineated string into appropraiet big ints
	public BigInteger[] bigIntsForStringRep(String rep)
	{
		StringTokenizer tokenizer = new StringTokenizer(rep,",");
		BigInteger[] array = new BigInteger[tokenizer.countTokens()];
		
		int i = 0;
		while(tokenizer.hasMoreTokens())
		{
			array[i] = new BigInteger(tokenizer.nextToken());
			i++;
		}
		
		return array;
	}
	
	//calculates the nth prime
	private BigInteger nthPrime(BigInteger nth)
	{
		if(nth.compareTo(BigInteger.ZERO) <= 0)
			throw new IllegalArgumentException("N in Nth prime must be strictly greater than 0");
	
		BigInteger two = new BigInteger("2");
	
		BigInteger current = two;
		if(nth.equals(BigInteger.ONE))
			return current;
		else
			current = current.add(BigInteger.ONE); //now we're three
			
		if(nth.equals(two))
			return current;
		
		BigInteger count = two; //we have currently found the second prime. we are going to start looking
								//for the third prime
								
		while(!count.equals(nth))
		{
			current = current.add(two);
			if(isPrime(current))
				count = count.add(BigInteger.ONE);
		}
		
		return current;
	}
	
	//checks if p is a prime
	private boolean isPrime(BigInteger p)
	{
		BigInteger two = new BigInteger("2");
		BigInteger divisor = two;
	
		if(p.compareTo(two) == -1)
			return false;
		else if(p.equals(two))
			return true;
		else if(p.mod(divisor).equals(BigInteger.ZERO))
			return false;
			
		divisor = divisor.add(BigInteger.ONE);
		
		while(divisor.multiply(divisor).compareTo(p) <= 0)
		{
			if(p.mod(divisor).equals(BigInteger.ZERO))
				return false;
		
			divisor  = divisor.add(two);
		}
		
		return true;
	}
}

[beamso]

Originally posted by Ghoser777:
Okay, I get what the problem is now... I just don't know a good fix for it.

If person A has public mod of 30 and person B has public mod of 21, then the scenario is something like this:

encrypt(M, key, 30) (value will be between 0 and 29)
encrypt(M, key, 21) (takes a value from 0 to 29 and converts it to a value from 0 to 20)
encrypt(M, key, 21) (takes a value from 0 to 20 and converts it to a value from 0 to 20)
encrypt(M, key, 30) (takes a value from 0 to 20 and converts it to a value from 0 to 29)

Now here's where things get ugly - the middle two operations are suppose to undo each other - so after them, we should be back to where we were after only on encrypt call. Unfortunately, if the first call to encrypt leaves us with an int between 21 and 29 (possible), then the next two calls of encrypt will not return us back to where we want to be. Instead we will end up with a value between 0 and 20... which is why I keep getting garbage after the final encrypt call.

Okay, now that I've isolated the problem (I hope), does anyone have an idea of how to solve it?

Okay... I was told this one in class last night. The steps you outline above are signing with the sender's private key and then encrypting with the recipient's public key.

As the recipient's public key is smaller than the senders, the input may undergo a modulus operation prior to the exponentiation under modulus operation. This can result in the incorrect decryption of the message.

What you can do in the above case is perform the operations in reverse, ie. encrypt then sign. Code your algorithm to detect this case (in encryption and decryption) and there shouldn't be any problems with the decryption returning unexpected results.