CODEWITHSUNDEEP
javaalgorithmencryptionmodulo
Scotty Skidmore
Scotty Skidmore

Reputation: 23

Trying to Determine a simple Decryption algorithm in Java

I have been struggling to figure out the a simple decryption algorithm for the following encryption method in Java:

/**
 * Returns the encryption of the given card number using the given keys.
 * Precondition: it can be assumed that cardNum is a valid numeric string,
 * k1 is a positive integer at most 9, and
 * k2 is a positive integer at most 9.
 * Postcondition: the string returned is the encryption of cardNum using keys
 * k1 and k2
 */
public static String encrypt (String cardNum, int k1, int k2) {

    int currentNum;
    long encryptedNum;
    String cryptogram = "";
    for (int i = 0; i < cardNum.length(); i++) {
        currentNum = Character.getNumericValue(cardNum.charAt(i));
        encryptedNum = (k1 * currentNum + k2) % 10;//the encryption algorithm
        cryptogram += encryptedNum;//add the encrypted number to the cryptogram
    }
    return cryptogram;
}

The previous encryption method is used to encrypt a Credit Card number of up to 16 digits and the aim is to create a method to reverse the algorithm and to retrieve the original card number.

I am also aware that for certain values of k1 and k2 there is no possible decryption due to the using of modulo 10 at the end of the encryption, because of this it is also part of the assignment to figure out which values of k1 and k2 can be decrypted. Then, write a method to decrypt the cardNum assuming a valid value of k1 and k2 are used

The following is as far as I have managed to get with the decrypt method and I have also not been able to determine what the valid values of k1 and k2 are.

/**
 * Returns the decryption of the given cryptogram using the given keys.
 * Precondition: it can be assumed that cryptogram is a valid numeric string,
 * k1 is a valid first encryption key,
 * k2 is a valid second encryption key.
 * Postcondition: the string returned is the decryption of cryptogram
 * using keys k1 and k2
 */
public static String decrypt (String cryptogram, int k1, int k2) {

    int currentNum;
    long decryptedNum;
    String cardNum = "";
    for (int i = 0; i < cryptogram.length(); i++) {
        currentNum = Character.getNumericValue(cryptogram.charAt(i));
        decryptedNum = (currentNum - k2)/k1;//the decryption algorithm
        cardNum += decryptedNum;//add the decrypted number to the cardNum
    }
    return cardNum;
}

Upvotes: 1

Views: 566

Answers (1)

Perseids
Perseids

Reputation: 13240

Let's start with reasons why decryption might fail.

  • First, there could be a practical problem, that for some values k1, k2 one could theoretically write a decryption algorithm, but in practice all know algorithms are to slow to be useful. (An example for such an algorithm would be the "encryption" function e(m,k)=SHA512(k||m) that takes any 16 byte message m, any 16 byte key k and outputs the SHA512 hash of the concatenation of k and m. I've put encryption in hyphens, as a condition for something being an encryption function is that there is an effective decryption function.) Spoiler: Your function does not fall in the first category.
  • Second, it is mathematical impossible to decrypt some values. This can happen, when with the same key(s) k1,k2 two message cardNum1 and cardNum2 get "encrypted" to the same value cryptogram. Thus later on, given cryptogram and the key(s), you can't decide which value was the original value. This is the problem you face. And the property you want to achieve is called "injectivity" (no two values get mapped to the same image).

Now, the next step to realize is that encryption gets broken down on a digit-by-digit basis. So if you have a problem with encryption or decryption of the whole credit card number it will manifest if and only if you have a problem with a single digit.

Another ingredient you need to know is an important property of modulo arithmetic. If you have any two basic operations A and B (for example + and *) for any three integers x,y,z the following identity holds: (x A y) B z % 10 = ((x A y) % 10) B z %10. That is you can apply the modulo calculation after each step or once at the end and the result will stay the same. For example (5*100 % 10) * 12 % 10 = (5*100)*12 % 10. You can even reduce each number modulo 10 first: 5*100 % 10 = 5*(100%10) %10 = 0.

With this you can already invert part of the encryption function: (k1 * currentNum) % 10 = (k1 * currentNum + k2 - k2) % 10 = (((k1 * currentNum + k2) % 10) - k2) % 10 = (encryptedNum - k2) %10.

What remains to do is to invert the multiplication operation. This part I would want to leave for you. You can already guess that for some values of k1 two values currentNum1 and currentNum2 will have the same result (k1 * currentNum) % 10. As (k1 * currentNum) % 10 = ((k1%10) * currentNum) % 10 there are only 10 interesting values for k1. Try each of these with each of the possible values of currentNum. With Java printing the 10 tables of 10 numbers should be a simple task. Then try to find out what those k1 for which several currentNums result in the same values have in common with each other and with 10. Once you have a hunch, look up the Extended Euclidean Algorithm, especially the section on multiplicative inverses.

Upvotes: 1

Related Questions