凯撒密码卡方的困难
Difficulty with Caesar Cipher Chi-Squared
以防你对密码不熟悉。这个想法是能够通过移动字母表中的字母来编码消息。前任。 d 移动 3 -> a。然后能够使用破解方法解码消息。破解方法为每个可能的移位（其索引）创建一个充满卡方值的数组（与 table 中的自然字母频率相比），并检查哪个移位具有最小值。然后它获取这个值并使用这个移位量对其进行解码。
问题是我在错误的数组地址中获取了最小的卡方值，以便能够准确解码它。我不是在找人给我答案，只是为了我应该在我的代码中查找以进行更正的地方。
提前致谢。
import java.util.Arrays;
public class Cipher {
//alphabet frequency
static double[] table = {8.2, 1.5, 2.8, 4.3, 12.7, 2.2, 2.0, 6.1, 7.0, 0.2, 0.8, 4.0, 2.4, 6.7,
7.5, 1.9, 0.1, 6.0, 6.3, 9.1, 2.8, 1.0, 2.4, 0.2, 2.0, 0.1};
//convert letter to number
static int let2nat(char c)
{
return ((int) c) - 97;
}
//convert number to letter
static char nat2let(int code)
{
return (char) (code + 97);
}
//shift a letter to another letter shftAmt spaces away
static char shift(int shftAmt, char c)
{
if (let2nat(c) < 0 || let2nat(c) > 25)
return c;
return nat2let((let2nat(c) + shftAmt) % 26);
}
//encodes a string using the given shift amount
static String encode(int shftAmt, String str)
{
char[] encodedStr = new char[str.length()];
for(int i = 0; i < str.length(); i++)
encodedStr[i] = shift(shftAmt, str.charAt(i));
return new String(encodedStr);
}
//performs the inverse method to encode
static String decode(int shftAmt, String str)
{
char[] decodedStr = new char[str.length()];
for(int i = 0; i < str.length(); i++)
decodedStr[i] = shift(0 - shftAmt, str.charAt(i));
return new String(decodedStr);
}
//determines how many lowercase letters are in the string str
static int lowers(String str)
{
int count = 0;
for(int i = 0; i < str.length(); i++)
if(let2nat(str.charAt(i)) >= 0 && let2nat(str.charAt(i)) <= 25)
count++;
return count;
}
//calculates the number of a character in a string
static int count(char c, String str)
{
int counter = 0;
for(int i = 0; i < str.length(); i++)
if(c == str.charAt(i))
counter++;
return counter;
}
//calculates the percent off num1 to num2
static double percent(int num1, int num2)
{
return ((double) num1/num2 * 100);
}
//find the ratio frequency of all letters in the string str
static double[] freqs(String str)
{
double[] count = new double[26];
for(int i = 0; i < str.length(); i++)
if(let2nat(str.charAt(i)) >= 0 && let2nat(str.charAt(i)) <= 25)
count[let2nat(str.charAt(i))]++;
for(int i = 0; i < 26; i++)
count[i] = percent((int)count[i], lowers(str));
return count;
}
//rotates a list n places to the left
static double[] rotate(int n, double[] list)
{
int j = 0;
while(j<n){
double starter = list[0];
//shift one left
for(int i = 0; i < list.length-1; i++)
list[i] = list[i+1];
list[list.length-1] = starter;
j++;
}
return list;
}
//calculates the chi square value
static double chisqr(double[] os)
{
double chitotal = 0;
for(int i = 0; i < os.length; i++)
chitotal += ((Math.pow((os[i] - table[i]), 2)) / table[i]);
return chitotal;
}
//returns the first position at whcih a value occurs,if returns 999999 then it doesnt exist in the array
static int position(double a, double[] list)
{
for(int i = 0; i < list.length; i++)
if(list[i] == a)
return i;
return 999999;
}
static String crack(String str)
{
double[] frequencies = freqs(str);
double[] chisqrValues = new double[26];
for(int i = 0; i < 26; i++)
chisqrValues[i] = chisqr(rotate(i, frequencies));
int smallestIndex = 0;
for(int i = 1; i < 26; i++)
if(chisqrValues[i] < chisqrValues[smallestIndex])
smallestIndex = i;
return decode(smallestIndex, str);
}
public static void main(String[] args)
{
System.out.println(crack(encode(3, "haskellisfun")));
}
}
如评论中所述，当使用负数作为索引参数时，您的移位代码是错误的，这是因为在使用 % 运算符时 Java 如何处理负值.为了安全起见，您应该这样做：
// shift a letter to another letter shftAmt spaces away
static char shift(int shftAmt, char c) {
if (let2nat(c) < 0 || let2nat(c) > Z_TO_A - 1) {
return c;
} else {
// do a safe shift
int result = (let2nat(c) + shftAmt) % Z_TO_A;
result += Z_TO_A;
result %= Z_TO_A;
return nat2let(result);
}
}
但正如评论中所提到的，这不是导致您的错误的原因，要找到该错误，您应该测试每个方法，最好使用单元测试，如果没有，则使用您自己的测试方法，以确保它们都按预期运行，如果没有，至少允许您隔离错误，这将使您在解决问题的道路上迈出一半。
顺便说一句，我自己对这个问题的看法是不要像您的代码那样忽略大写字母，但由于它们是文本字母频率的一部分，因此在计算我们自己的字母频率时应该使用它们。像这样的东西可能会很好用：
/**
*
* @author hovercraft
* {@link
*/
public class Cipher2 {
// just ban "magic" numbers
public static final int A_VALUE = (int) 'a';
public static final int Z_TO_A = (int) ('z' - 'a') + 1;
// alphabet frequency
static double[] table = { 8.2, 1.5, 2.8, 4.3, 12.7, 2.2, 2.0, 6.1, 7.0, 0.2,
0.8, 4.0, 2.4, 6.7, 7.5, 1.9, 0.1, 6.0, 6.3, 9.1, 2.8, 1.0, 2.4, 0.2,
2.0, 0.1 };
// convert letter to number
static int let2nat(char c) {
return ((int) c) - A_VALUE;
}
// convert number to letter
static char nat2let(int code) {
return (char) (code + A_VALUE);
}
// shift a letter to another letter shftAmt spaces away
static char shift(int shftAmt, char c) {
if (let2nat(c) < 0 || let2nat(c) > Z_TO_A - 1) {
return c;
} else {
// do a safe shift
int result = (let2nat(c) + shftAmt) % Z_TO_A;
result += Z_TO_A;
result %= Z_TO_A;
return nat2let(result);
}
}
private static String crack(String encrypted) {
int[] letterCount = new int[Z_TO_A];
for (char c : encrypted.toCharArray()) {
letterCount[let2nat(c)]++;
}
double[] letterFrequency = new double[Z_TO_A];
for (int i = 0; i < letterCount.length; i++) {
letterFrequency[i] = (double) letterCount[i] * 100 / Z_TO_A;
}
int index = 0;
double minChiSqrSum = calcChiSqrSum(index, letterFrequency);
for (int i = 0; i < Z_TO_A; i++) {
double chiSqrSum = calcChiSqrSum(i, letterFrequency);
if (chiSqrSum < minChiSqrSum) {
minChiSqrSum = chiSqrSum;
index = i;
}
}
return encode(index, encrypted);
}
private static double calcChiSqrSum(int i, double[] letterFrequency) {
double sum = 0.0;
for (int j = 0; j < letterFrequency.length; j++) {
double observed = letterFrequency[j];
int tableIndex = (i + j + Z_TO_A) % Z_TO_A;
double expected = table[tableIndex];
double delta = observed - expected;
double chiSqr = delta * delta / expected;
sum += chiSqr;
}
return sum;
}
private static String encode(int shift, String text) {
StringBuilder sb = new StringBuilder();
for (char c : text.toCharArray()) {
// convert all upper case to lower case
// this is a judgment call on my part
c = Character.toLowerCase(c);
if (let2nat(c) >= 0 && let2nat(c) < Z_TO_A) {
sb.append(shift(shift, c));
}
}
return sb.toString();
}
public static void main(String[] args) {
String test1 = "Hello world. How is it going? It's going fine with me";
String test2 = "When, in the course of human events, it becomes "
+ "necessary for one portion of the family of man to assume "
+ "among the people of the earth a position different from "
+ "that which they have hitherto occupied, but one to which "
+ "the laws of nature and of nature's God entitle them, "
+ "a decent respect to the opinions of mankind";
// let's throw it for a complete loop: ... but it works!
String test3 = "Lorem ipsum dolor sit amet, consectetur adipiscing "
+ "elit, sed do eiusmod tempor incididunt ut labore et dolore "
+ "magna aliqua. Ut enim ad minim veniam, quis nostrud "
+ "exercitation ullamco laboris nisi ut aliquip ex ea commodo "
+ "consequat. Duis aute irure dolor in reprehenderit in "
+ "voluptate velit esse cillum dolore eu fugiat nulla pariatur. "
+ "Excepteur sint occaecat cupidatat non proident, sunt in "
+ "culpa qui officia deserunt mollit anim id est laborum.";
// an unfair test:
String test4 = "abcdefghijklmnopqrstuvwxyz";
String test5 = "haskellisfun";
String[] tests = { test1, test2, test3, test4, test5 };
for (String test : tests) {
System.out.println(crack(encode(6, test)));
}
}
}
以防你对密码不熟悉。这个想法是能够通过移动字母表中的字母来编码消息。前任。 d 移动 3 -> a。然后能够使用破解方法解码消息。破解方法为每个可能的移位（其索引）创建一个充满卡方值的数组（与 table 中的自然字母频率相比），并检查哪个移位具有最小值。然后它获取这个值并使用这个移位量对其进行解码。
问题是我在错误的数组地址中获取了最小的卡方值，以便能够准确解码它。我不是在找人给我答案，只是为了我应该在我的代码中查找以进行更正的地方。
提前致谢。
import java.util.Arrays;
public class Cipher {
//alphabet frequency
static double[] table = {8.2, 1.5, 2.8, 4.3, 12.7, 2.2, 2.0, 6.1, 7.0, 0.2, 0.8, 4.0, 2.4, 6.7,
7.5, 1.9, 0.1, 6.0, 6.3, 9.1, 2.8, 1.0, 2.4, 0.2, 2.0, 0.1};
//convert letter to number
static int let2nat(char c)
{
return ((int) c) - 97;
}
//convert number to letter
static char nat2let(int code)
{
return (char) (code + 97);
}
//shift a letter to another letter shftAmt spaces away
static char shift(int shftAmt, char c)
{
if (let2nat(c) < 0 || let2nat(c) > 25)
return c;
return nat2let((let2nat(c) + shftAmt) % 26);
}
//encodes a string using the given shift amount
static String encode(int shftAmt, String str)
{
char[] encodedStr = new char[str.length()];
for(int i = 0; i < str.length(); i++)
encodedStr[i] = shift(shftAmt, str.charAt(i));
return new String(encodedStr);
}
//performs the inverse method to encode
static String decode(int shftAmt, String str)
{
char[] decodedStr = new char[str.length()];
for(int i = 0; i < str.length(); i++)
decodedStr[i] = shift(0 - shftAmt, str.charAt(i));
return new String(decodedStr);
}
//determines how many lowercase letters are in the string str
static int lowers(String str)
{
int count = 0;
for(int i = 0; i < str.length(); i++)
if(let2nat(str.charAt(i)) >= 0 && let2nat(str.charAt(i)) <= 25)
count++;
return count;
}
//calculates the number of a character in a string
static int count(char c, String str)
{
int counter = 0;
for(int i = 0; i < str.length(); i++)
if(c == str.charAt(i))
counter++;
return counter;
}
//calculates the percent off num1 to num2
static double percent(int num1, int num2)
{
return ((double) num1/num2 * 100);
}
//find the ratio frequency of all letters in the string str
static double[] freqs(String str)
{
double[] count = new double[26];
for(int i = 0; i < str.length(); i++)
if(let2nat(str.charAt(i)) >= 0 && let2nat(str.charAt(i)) <= 25)
count[let2nat(str.charAt(i))]++;
for(int i = 0; i < 26; i++)
count[i] = percent((int)count[i], lowers(str));
return count;
}
//rotates a list n places to the left
static double[] rotate(int n, double[] list)
{
int j = 0;
while(j<n){
double starter = list[0];
//shift one left
for(int i = 0; i < list.length-1; i++)
list[i] = list[i+1];
list[list.length-1] = starter;
j++;
}
return list;
}
//calculates the chi square value
static double chisqr(double[] os)
{
double chitotal = 0;
for(int i = 0; i < os.length; i++)
chitotal += ((Math.pow((os[i] - table[i]), 2)) / table[i]);
return chitotal;
}
//returns the first position at whcih a value occurs,if returns 999999 then it doesnt exist in the array
static int position(double a, double[] list)
{
for(int i = 0; i < list.length; i++)
if(list[i] == a)
return i;
return 999999;
}
static String crack(String str)
{
double[] frequencies = freqs(str);
double[] chisqrValues = new double[26];
for(int i = 0; i < 26; i++)
chisqrValues[i] = chisqr(rotate(i, frequencies));
int smallestIndex = 0;
for(int i = 1; i < 26; i++)
if(chisqrValues[i] < chisqrValues[smallestIndex])
smallestIndex = i;
return decode(smallestIndex, str);
}
public static void main(String[] args)
{
System.out.println(crack(encode(3, "haskellisfun")));
}
}
如评论中所述，当使用负数作为索引参数时，您的移位代码是错误的，这是因为在使用 % 运算符时 Java 如何处理负值.为了安全起见，您应该这样做：
// shift a letter to another letter shftAmt spaces away
static char shift(int shftAmt, char c) {
if (let2nat(c) < 0 || let2nat(c) > Z_TO_A - 1) {
return c;
} else {
// do a safe shift
int result = (let2nat(c) + shftAmt) % Z_TO_A;
result += Z_TO_A;
result %= Z_TO_A;
return nat2let(result);
}
}
但正如评论中所提到的，这不是导致您的错误的原因，要找到该错误，您应该测试每个方法，最好使用单元测试，如果没有，则使用您自己的测试方法，以确保它们都按预期运行，如果没有，至少允许您隔离错误，这将使您在解决问题的道路上迈出一半。
顺便说一句，我自己对这个问题的看法是不要像您的代码那样忽略大写字母，但由于它们是文本字母频率的一部分，因此在计算我们自己的字母频率时应该使用它们。像这样的东西可能会很好用：
/**
*
* @author hovercraft
* {@link
*/
public class Cipher2 {
// just ban "magic" numbers
public static final int A_VALUE = (int) 'a';
public static final int Z_TO_A = (int) ('z' - 'a') + 1;
// alphabet frequency
static double[] table = { 8.2, 1.5, 2.8, 4.3, 12.7, 2.2, 2.0, 6.1, 7.0, 0.2,
0.8, 4.0, 2.4, 6.7, 7.5, 1.9, 0.1, 6.0, 6.3, 9.1, 2.8, 1.0, 2.4, 0.2,
2.0, 0.1 };
// convert letter to number
static int let2nat(char c) {
return ((int) c) - A_VALUE;
}
// convert number to letter
static char nat2let(int code) {
return (char) (code + A_VALUE);
}
// shift a letter to another letter shftAmt spaces away
static char shift(int shftAmt, char c) {
if (let2nat(c) < 0 || let2nat(c) > Z_TO_A - 1) {
return c;
} else {
// do a safe shift
int result = (let2nat(c) + shftAmt) % Z_TO_A;
result += Z_TO_A;
result %= Z_TO_A;
return nat2let(result);
}
}
private static String crack(String encrypted) {
int[] letterCount = new int[Z_TO_A];
for (char c : encrypted.toCharArray()) {
letterCount[let2nat(c)]++;
}
double[] letterFrequency = new double[Z_TO_A];
for (int i = 0; i < letterCount.length; i++) {
letterFrequency[i] = (double) letterCount[i] * 100 / Z_TO_A;
}
int index = 0;
double minChiSqrSum = calcChiSqrSum(index, letterFrequency);
for (int i = 0; i < Z_TO_A; i++) {
double chiSqrSum = calcChiSqrSum(i, letterFrequency);
if (chiSqrSum < minChiSqrSum) {
minChiSqrSum = chiSqrSum;
index = i;
}
}
return encode(index, encrypted);
}
private static double calcChiSqrSum(int i, double[] letterFrequency) {
double sum = 0.0;
for (int j = 0; j < letterFrequency.length; j++) {
double observed = letterFrequency[j];
int tableIndex = (i + j + Z_TO_A) % Z_TO_A;
double expected = table[tableIndex];
double delta = observed - expected;
double chiSqr = delta * delta / expected;
sum += chiSqr;
}
return sum;
}
private static String encode(int shift, String text) {
StringBuilder sb = new StringBuilder();
for (char c : text.toCharArray()) {
// convert all upper case to lower case
// this is a judgment call on my part
c = Character.toLowerCase(c);
if (let2nat(c) >= 0 && let2nat(c) < Z_TO_A) {
sb.append(shift(shift, c));
}
}
return sb.toString();
}
public static void main(String[] args) {
String test1 = "Hello world. How is it going? It's going fine with me";
String test2 = "When, in the course of human events, it becomes "
+ "necessary for one portion of the family of man to assume "
+ "among the people of the earth a position different from "
+ "that which they have hitherto occupied, but one to which "
+ "the laws of nature and of nature's God entitle them, "
+ "a decent respect to the opinions of mankind";
// let's throw it for a complete loop: ... but it works!
String test3 = "Lorem ipsum dolor sit amet, consectetur adipiscing "
+ "elit, sed do eiusmod tempor incididunt ut labore et dolore "
+ "magna aliqua. Ut enim ad minim veniam, quis nostrud "
+ "exercitation ullamco laboris nisi ut aliquip ex ea commodo "
+ "consequat. Duis aute irure dolor in reprehenderit in "
+ "voluptate velit esse cillum dolore eu fugiat nulla pariatur. "
+ "Excepteur sint occaecat cupidatat non proident, sunt in "
+ "culpa qui officia deserunt mollit anim id est laborum.";
// an unfair test:
String test4 = "abcdefghijklmnopqrstuvwxyz";
String test5 = "haskellisfun";
String[] tests = { test1, test2, test3, test4, test5 };
for (String test : tests) {
System.out.println(crack(encode(6, test)));
}
}
}