Breaking The Caesar Cipher

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, я использовал HashMap, который связывает символы с их probability of occurence in English text.