打破凯撒密码

Question

import java.util.Scanner;

public class CaesarCipher {

public static void main(String[] args) {
    // TODO Auto-generated method stub
Scanner input = new Scanner (System.in);   

    System.out.println("Enter the encrypted text :"); 
String cryptedtext = input.nextLine();                
    cryptedtext = cryptedtext.toLowerCase();                
String[] array = new String[cryptedtext.length()];        
    for (int i = 97; i < 123; i++)          
    {           
        int mostFrequent = 0;       
        for (int j = 0; j < cryptedtext.length(); j++) 
        {           
            if (cryptedtext.charAt(j) == i){    
                ++mostFrequent;                 
                }       
            }           
        System.out.println((char) i + " is showing " + mostFrequent + " times ");                                                               
        } 
    } 
}

我试图打破密码，我必须计算一个字母在单词或句子中重复多少次。我只需要将英语单词/句子翻译成英语中的实际句子，我真的不知道该怎么做。我必须写一些加密的东西并计算重复的字母（到目前为止我已经完成了），但我实际上并不知道如何解密它。

Answer 1

凯撒密码通过用已知密钥移动所有字母（a-z）来加密消息。有26个字符，有26种可能性。蛮力方法将扫描所有最简单的密钥（1-26），为每个密钥生成解密文本。其中一个解密文本将是可读的，这将是解决方案。在这种情况下，不需要使用字频。下一步的挑战是告诉计算机如何为您选择解决方案。

伪代码

key=1
while key<27
   create a string/array of all letters shifted by key
   print/store results + key
   increment key

Answer 2

其中一个可能的解决方案是强制键并返回那些在预定义字典中输出最多单词的List。你可以找到这样一本词典here。

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;


public class CeasarCipher {

    final private static char fromChar = ' '; //space character
    final private static char toChar = '~'; //~
    final private static char numOfChars = toChar - fromChar + 1;

    final private static String dictionaryFilePath = "ENG_DICTIONARY.TXT";
    private static Set<String> dictionary;

    //encrypt with shiftKey
    //decrypt with numOfChars - shiftKey
    public static char[] ceasar(char [] clearText, int shiftKey) {
        char[] cipherText = new char[clearText.length];
        for (int i=0; i < clearText.length; i++) {
            cipherText[i] = (char) (clearText[i] + shiftKey);
            if (cipherText[i] > toChar) {
                cipherText[i] -= numOfChars;
            }
        }
        return cipherText;
    }

    private static Set<String> getDictionary () {
        if (dictionary != null)
            return dictionary;
        Scanner file = null;
        try {
            file = new Scanner(new File(dictionaryFilePath));
            dictionary = new HashSet<String>();
            // For each word in the input
            while (file.hasNext()) {
                // Convert the word to lower case, trim it and insert into the set
                dictionary.add(file.next().trim().toLowerCase());
            }
        } catch (FileNotFoundException e) {
            System.out.println("Cannot find dictionary file");
        } finally {
            file.close();
        }
        return dictionary;
    }

    //count number of words found in dictionary
    public static int evaluateMetric(String input) {
        //split String by space, punctuation
        String[] splitWords = input.split("[\\p{Punct}\\s]+");
        int match = 0;

        for (String s: splitWords) {
            if (getDictionary().contains(s)) {
                match++;
            }
        }
        return match;
    }

    //return the keys that seem to output most words than the rest
    public static List<Integer> heuristicCracker(char[] cipherText) {
        int[] matchesPerKeyArray = new int[numOfChars];
        for (int i = 0; i < numOfChars; i++) {
            char[] clear = ceasar(cipherText, numOfChars - i);
            matchesPerKeyArray[i] = evaluateMetric(String.valueOf(clear));
        }
        //find keys with most matches
        int max = Arrays.stream(matchesPerKeyArray).max().getAsInt();

        List<Integer> possibleKeys = new ArrayList<Integer>();
        for (int i = 0; i < numOfChars; i++) {
            if (matchesPerKeyArray[i] == max) {
                possibleKeys.add(i);
            }
        }
        return possibleKeys;
    }

    public static void main (String args[]) {
        String a = "Please don't tell me you have a headache again!!";
        char[] res = ceasar(a.toCharArray(), 12);

        List<Integer> possibleKeys = heuristicCracker(res);
        System.out.println("--- Possible Keys/Decrypted ---");
        for (int i: possibleKeys) {
            String decrypted = String.valueOf(ceasar(res, (char) (numOfChars - i)));
            System.out.println(i + ": " + decrypted);
        }
    }
}

Answer 3

我已经使用这个简单的启发式函数来判断输入是否是英文明文，而没有实际的单词列表。

它运行得很好，我测试的所有英文明文得分都高于800，但通常超过1000.它有一个小缺陷，一个匈牙利文本也得分超过1000，其他人少于800.但它仍然有利于它的意图目的。

/** 
 * This heuristic function tells us that a decoded message is English plaintext or not
 * @param letters the percentage of letters a-z, A-Z in the text
 * @param frequency the average relative frequency of its letters
 * @param lowercase the percentage of lowercase letters among all letters
 * @param spaces the percentage of spaces in the whole text
 * @return the higher number it returns, the better the chance that the text is an English message
 */
public static int plainTextHeuristic(double letters, double frequency, double lowercase, double spaces) {
// the absence of lowercase makes it less likely that it's plaintext, although it's still possible
    final double LOWERCASE_CONST = 30; 
// the absence of spaces makes it much less likely, but still has some possibility
    final double SPACE_CONST = 1; 
    return (int) Math.round( letters * frequency * (LOWERCASE_CONST + lowercase) * (SPACE_CONST + spaces) / 1000 );
}

首先，我必须计算输入值。为了获得frequency，我使用了一个将字符与probability of occurence in English text相关联的HashMap。