Welcome to the MacNN Forums.

If this is your first visit, be sure to check out the FAQ by clicking the link above. You may have to register before you can post: click the register link above to proceed. To start viewing messages, select the forum that you want to visit from the selection below.

You are here: MacNN Forums > Software - Troubleshooting and Discussion > Developer Center > Demo Crypto Problem

Demo Crypto Problem
Thread Tools
Ghoser777
Professional Poster
Join Date: Dec 2000
Location: Chicago, Illinois
Status: Offline
Reply With Quote
May 20, 2004, 09:42 PM
 
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
Fresh-Faced Recruit
Join Date: Nov 2001
Location: Melboune, Australia
Status: Offline
Reply With Quote
May 21, 2004, 02:36 AM
 
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  (op)
Professional Poster
Join Date: Dec 2000
Location: Chicago, Illinois
Status: Offline
Reply With Quote
May 21, 2004, 06:33 AM
 
modPow gives me the exact same (wrong) answer - I was just calculating the modPow manually before. So strange...

Thanks,
Matt Fahrenbacher
     
Ghoser777  (op)
Professional Poster
Join Date: Dec 2000
Location: Chicago, Illinois
Status: Offline
Reply With Quote
May 21, 2004, 07:50 AM
 
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  (op)
Professional Poster
Join Date: Dec 2000
Location: Chicago, Illinois
Status: Offline
Reply With Quote
May 22, 2004, 07:33 PM
 
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  (op)
Professional Poster
Join Date: Dec 2000
Location: Chicago, Illinois
Status: Offline
Reply With Quote
May 23, 2004, 02:30 PM
 
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
Fresh-Faced Recruit
Join Date: Nov 2001
Location: Melboune, Australia
Status: Offline
Reply With Quote
May 24, 2004, 08:45 PM
 
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.
     
   
Thread Tools
 
Forum Links
Forum Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Top
Privacy Policy
All times are GMT -4. The time now is 02:34 PM.
All contents of these forums © 1995-2017 MacNN. All rights reserved.
Branding + Design: www.gesamtbild.com
vBulletin v.3.8.8 © 2000-2017, Jelsoft Enterprises Ltd.,