How to resolve the algorithm Vigenère cipher/Cryptanalysis step by step in the Java programming language

Problem Statement
Step by Step Solution
Sourcecode

Problem Statement

Given some text you suspect has been encrypted with a Vigenère cipher, extract the key and plaintext. There are several methods for doing this. See the Wikipedia entry for more information. Use the following encrypted text: Letter frequencies for English can be found here. Specifics for this task:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Vigenère cipher/Cryptanalysis step by step in the Java programming language

This Java code appears to be an implementation of the Vigenere cipher, a classic polyalphabetic substitution cipher that encrypts plaintext using a repeating key. Here's a detailed explanation:

Class Definition: The program defines a Java class named Vig.
Encoded Message:
- encodedMessage is a static string that holds a long encrypted message in uppercase letters. It is the message that will be decrypted.
Character Frequency Array:
- freq[] is a static array of doubles representing the expected frequencies of each letter in the English language. This array will be used to analyze the encrypted message.
Main Method:
- main method is the entry point of the program.
- It initializes arrays:
  - encoded: Character array to store the encrypted message.
  - key: Character array to store the potential key for decrypting.
  - txt: Integer array to store the numeric representations of characters in the encrypted message (after converting uppercase letters to numbers).
- It iterates through the encrypted message and extracts the characters into the encoded array.
- It creates an array txt for storing the numerical values of uppercase characters ('A' to 'Z') from the encoded message.
Key Length Estimation:
- It enters a loop from j = 1 to 30, where it tries different key lengths for the Vigenere cipher.
- For each key length j, it calculates a fitness value called fit using the freq_every_nth method. The fitness value measures how well the key matches the expected letter frequencies in English.
- It prints the fitness value, the key length, and the potential key found so far.
decrypt Method:
- This method is used to decrypt the encrypted text using a specified key. It takes two parameters:
  - text: The encrypted text.
  - key: The key used for decryption.
- The method iterates through the encrypted text and decrypts each character by shifting it based on the corresponding key character. The decrypted characters are concatenated to form the decrypted message.
best_match Method:
- This method is used to find the best rotation of a given array (b) to match another array (a). It calculates the least squared difference between the rotated array and the target array.
- The best rotation is returned, which represents the key used for decryption.
freq_every_nth Method:
- This method takes three parameters:
  - msg: An array of integers representing the encrypted message.
  - len: Length of the message.
  - interval: The key length being tested.
- The method iterates through the encrypted message at the specified interval and calculates the frequency of each character.
- It then finds the best rotation of the observed frequencies to match the expected letter frequencies in English.
- It returns the fitness value, which is a measure of how well the key matches the expected frequencies.
Key Estimation Process:
- The program iterates through different key lengths and uses the freq_every_nth method to estimate potential keys.
- It prints the fitness value and the potential key for each key length. The key with the lowest fitness value is likely to be the correct key.
Decryption:

After finding the best key, the program could use the decrypt method (which is currently not called in the code) to decrypt the encrypted message using the estimated key.

This code demonstrates the process of finding the key length and decrypting a Vigenere cipher. However, it does not complete the decryption by calling the decrypt method. You may need to modify the code to call the decrypt method with the estimated key to obtain the decrypted message.

Source code in the java programming language

public class Vig{
static String encodedMessage =
    "MOMUD EKAPV TQEFM OEVHP AJMII CDCTI FGYAG JSPXY ALUYM NSMYH VUXJE LEPXJ FXGCM JHKDZ RYICU HYPUS PGIGM OIYHF WHTCQ KMLRD ITLXZ LJFVQ GHOLW CUHLO MDSOE KTALU VYLNZ RFGBX PHVGA LWQIS FGRPH JOOFW GUBYI LAPLA LCAFA AMKLG CETDW VOELJ IKGJB XPHVG ALWQC SNWBU BYHCU HKOCE XJEYK BQKVY KIIEH GRLGH XEOLW AWFOJ ILOVV RHPKD WIHKN ATUHN VRYAQ DIVHX FHRZV QWMWV LGSHN NLVZS JLAKI FHXUF XJLXM TBLQV RXXHR FZXGV LRAJI EXPRV OSMNP KEPDT LPRWM JAZPK LQUZA ALGZX GVLKL GJTUI ITDSU REZXJ ERXZS HMPST MTEOE PAPJH SMFNB YVQUZ AALGA YDNMP AQOWT UHDBV TSMUE UIMVH QGVRW AEFSP EMPVE PKXZY WLKJA GWALT VYYOB YIXOK IHPDS EVLEV RVSGB JOGYW FHKBL GLXYA MVKIS KIEHY IMAPX UOISK PVAGN MZHPW TTZPV XFCCD TUHJH WLAPF YULTB UXJLN SIJVV YOVDJ SOLXG TGRVO SFRII CTMKO JFCQF KTINQ BWVHG TENLH HOGCS PSFPV GJOKM SIFPR ZPAAS ATPTZ FTPPD PORRF TAXZP KALQA WMIUD BWNCT LEFKO ZQDLX BUXJL ASIMR PNMBF ZCYLV WAPVF QRHZV ZGZEF KBYIO OFXYE VOWGB BXVCB XBAWG LQKCM ICRRX MACUO IKHQU AJEGL OIJHH XPVZW JEWBA FWAML ZZRXJ EKAHV FASMU LVVUT TGK";
 
final static double freq[] = {
    0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015,
    0.06094, 0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 0.06749,
    0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758,
    0.00978, 0.02360, 0.00150, 0.01974, 0.00074
};
 

public static void main(String[] args) {
    int lenghtOfEncodedMessage = encodedMessage.length();
    char[] encoded = new char [lenghtOfEncodedMessage] ;
    char[] key =  new char [lenghtOfEncodedMessage] ;

    encodedMessage.getChars(0, lenghtOfEncodedMessage, encoded, 0);
    int txt[] = new int[lenghtOfEncodedMessage];
    int len = 0, j;

    double fit, best_fit = 1e100;
 
    for (j = 0; j < lenghtOfEncodedMessage; j++)
        if (Character.isUpperCase(encoded[j]))
            txt[len++] = encoded[j] - 'A';
 
    for (j = 1; j < 30; j++) {
        fit = freq_every_nth(txt, len, j, key);
        System.out.printf("%f, key length: %2d ", fit, j);
            System.out.print(key);
        if (fit < best_fit) {
            best_fit = fit;
            System.out.print(" <--- best so far");
        }
        System.out.print("\n");

    }
}


    static String decrypt(String text, final String key) {
        String res = "";
        text = text.toUpperCase();
        for (int i = 0, j = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            if (c < 'A' || c > 'Z') continue;
            res += (char)((c - key.charAt(j) + 26) % 26 + 'A');
            j = ++j % key.length();
        }
        return res;
    }

static int best_match(final double []a, final double []b) {
    double sum = 0, fit, d, best_fit = 1e100;
    int i, rotate, best_rotate = 0;
    for (i = 0; i < 26; i++)
        sum += a[i];
    for (rotate = 0; rotate < 26; rotate++) {
        fit = 0;
        for (i = 0; i < 26; i++) {
            d = a[(i + rotate) % 26] / sum - b[i];
            fit += d * d / b[i];
        }
 
        if (fit < best_fit) {
            best_fit = fit;
            best_rotate = rotate;
        }
    }
 
    return best_rotate;
}
 
static double freq_every_nth(final int []msg, int len, int interval, char[] key) {
    double sum, d, ret;
    double  [] accu = new double [26];
    double  [] out = new double [26];
    int i, j, rot;
 
    for (j = 0; j < interval; j++) {
        for (i = 0; i < 26; i++)
            out[i] = 0;
        for (i = j; i < len; i += interval)
            out[msg[i]]++;
	rot = best_match(out, freq);
	try{
            key[j] = (char)(rot + 'A');
	} catch (Exception e) {
		System.out.print(e.getMessage());
	}
        for (i = 0; i < 26; i++)
            accu[i] += out[(i + rot) % 26];
    }
 
    for (i = 0, sum = 0; i < 26; i++)
        sum += accu[i];
 
    for (i = 0, ret = 0; i < 26; i++) {
        d = accu[i] / sum - freq[i];
        ret += d * d / freq[i];
    }
 
    key[interval] = '\0';
    return ret;
}
 
}

You may also check:How to resolve the algorithm Pi step by step in the Kotlin programming language
You may also check:How to resolve the algorithm Multiple distinct objects step by step in the Phix programming language
You may also check:How to resolve the algorithm Knapsack problem/0-1 step by step in the FreeBASIC programming language
You may also check:How to resolve the algorithm Parallel calculations step by step in the Raku programming language
You may also check:How to resolve the algorithm Knapsack problem/0-1 step by step in the Groovy programming language

How to resolve the algorithm Vigenère cipher/Cryptanalysis step by step in the Java programming language

Table of Contents

Problem Statement

Step by Step solution about How to resolve the algorithm Vigenère cipher/Cryptanalysis step by step in the Java programming language

Source code in the java programming language