我有一个已知大小的 key ，例如:
String key = "A B C"; // Unknown / This is what I need to guess in the end
int keySize = key.length(); // Known
我知道 key 和文本都只包含以下字符:
String AVAILABLE_CHARS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ .,!?-"; // Known
我有一些文本是通过使用 key 对文本进行异或来编码的。 encode 方法执行以下操作:检查键和大写文本是否不为空也不为空且仅包含有效字符，然后创建字符串的 UTF-8 字节数组并将它们异或在一起以一个字节[]。 (如果文本比 key 长， key 将再次重复。)
byte[][] encryptedTexts = new byte[5][];
// The original texts are Unknown, the encrypted byte-arrays are Known
encryptedTexts[0] = encode(key, "THIS IS A TEST");
encryptedTexts[1] = encode(key, "This is another test!"); // Note: encode first makes the String UPPERCASE, so this encrypts correctly.
encryptedTexts[2] = encode(key, "SOME OTHER RANDOM TEXT");
encryptedTexts[3] = encode(key, "AND LET'S SEE HOW THIS GOES"); // Should return null since ' in LET'S isn't valid
encryptedTexts[0] = encode(key, "OK, THAT WILL BE ENOUGH FOR NOW..");
编码后我有以下加密的字节数组(Arrays.toString(byte_array)):
ENCRYPTED TEXT 1: [21, 104, 11, 115, 99, 8, 115, 98, 97, 99, 21, 101, 17, 116]
ENCRYPTED TEXT 2: [21, 104, 11, 115, 99, 8, 115, 98, 97, 13, 14, 116, 10, 101, 17, 97, 116, 7, 115, 23, 96]
ENCRYPTED TEXT 3: [18, 111, 15, 101, 99, 14, 116, 10, 101, 17, 97, 114, 3, 110, 7, 14, 109, 98, 116, 6, 25, 116]
ENCRYPTED TEXT 4: null
ENCRYPTED TEXT 5: [14, 107, 110, 0, 23, 9, 97, 22, 0, 20, 8, 108, 14, 0, 1, 4, 0, 7, 110, 12, 20, 103, 10, 0, 5, 14, 114, 98, 110, 12, 22, 14, 108]
那么，现在我的问题是:如何仅通过知道加密文本和 key 大小来获取 key ？
一些想法:
- > I know you can easily get the key by XOR-ing the original text with the encrypted text. Problem: I don't have the original text.
- > I know you can partly decrypt one text by using another text's repeated words (like
" the ") and then guess the other part. Problems: This only works when the text(s) are pretty long, contain the guessed word (like" the ") and ARE words in general. This method won't work when the original texts are also just randomly generated characters, even when the size is very large / 100,000+. - > I know that XOR-ing the same characters with each other will return a 0-byte. In the example above, with the 5th encrypted text, we see a few 0's. When a 0 is found this means that the original text and the key share the same character at the same index. Problem: I don't have the original text.
如果您只知道加密的字节数组(无限 数量)和 key 大小，是否有可能获得 key ？如果是，最好的方法是什么？
一些注意事项:
- 我不关心解密加密文本，我的目标是获取 key 字符串。
- 如果您要发布示例代码，请使用 Java，因为这是我正在使用的编程语言。
- 这只是一项作业(不是针对学校，而是针对 Java cursus)，所以我不打算用它破解任何东西。 (尽管我可能会 mock 那些使用相同 key 进行 XOR 加密的人。XOR 加密只能使用与文本大小相同或更大的真正随机生成的 key 来完成，也称为 一次性一密本。引用:“使用真正随机的 key ，结果是一次性一密本，即使在理论上也是牢不可破的。”[ source ].)
编辑 1:
好吧，忘掉随机生成的未加密文本，让我们假设我有一个已加密的大英文文本。如果我事先知道文本是英文的，我可以使用 Letter Frequency Analysis Table .那么我不仅知道加密文本和 key 大小，而且还知道这些字母的频率。我怎样才能使用这个额外的频率来获得 key 。 (假设我拥有无限 数量的加密文本，用于使用 XOR 解密重新创建/猜测 key 。)
最佳答案
您可能只对 key 感兴趣，但请尝试着重于获取明文之一。这当然会简单地产生 key 。
首先将成对的明文异或在一起(如果它们的长度不同，则截断最长的)。这将删除 key 并为您留下成对的英语句子(-片段)异或在一起。
假设密文无限，我们可以采取一种简单的方法:
取一个密文并将其与其他 1000 个密文异或。查看大约 90% 的对中第 6 位为 1 的所有位置。这些位置必须在第一个密文中有一个 [ .,!?-] 并且有大约 80% 的概率是空格。假设这是一个空格，如果为真，则计算等效的键字节必须是什么。
对一堆其他密文重复此操作，您将能够确定 [ .,!?-] 中的哪一个实际上是空格(~80% 将在此处具有相同的键值)。
这是 Java 中的一个实现。它通常使用几千条消息来找到 key :
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Random;
public class MultitimePad {
private final static int SPACE_TEST_NUM = 10;
private final static int SPACE_TEST_MIN = 8;
private final static int KEY_GUESS_MIN = 10;
private final static double KEY_GUESS_MIN_PERCENTAGE = 0.8;
public static void main(String[] args) throws IOException {
MultitimePad p = new MultitimePad();
byte[] key = new byte[256];
new Random().nextBytes(key);
byte[][] messages = p.generate(key);
byte[] solvedKey = p.solve(key.length, messages);
if (compareBytes(key, solvedKey)) {
System.out.println("Success");
} else {
System.out.println("Failure");
}
}
private byte[][] generate(byte[] key) throws IOException {
byte[] data = Files.readAllBytes(Paths.get("src/ulysses.txt"));
byte[] filteredData = new byte[data.length];
int filteredDataLength = 0;
for (int i = 0; i < data.length; i++) {
byte p = data[i];
if (p >= 'a' && p <= 'z') {
filteredData[filteredDataLength] = (byte) (p - 'a' + 'A');
filteredDataLength++;
} else if (p >= 'A' && p <= 'Z') {
filteredData[filteredDataLength] = p;
filteredDataLength++;
} else if (p == ' ' || p == '.' || p == ',' || p == '!' || p == '?' || p == '-') {
filteredData[filteredDataLength] = p;
filteredDataLength++;
}
}
int numMessages = filteredDataLength / key.length;
byte[][] messages = new byte[numMessages][];
for (int i = 0; i < numMessages; i++) {
messages[i] = new byte[key.length];
for (int j = 0; j < key.length; j++) {
byte p = filteredData[i * key.length + j];
messages[i][j] = (byte) (p ^ key[j]);
}
}
return messages;
}
private static boolean compareBytes(byte[] b1, byte[] b2) {
if (b1.length != b2.length) {
return false;
}
for (int i = 0; i < b1.length; i++) {
if (b1[i] != b2[i]) {
return false;
}
}
return true;
}
private byte[] solve(int length, byte[][] messages) {
byte[] key = new byte[length];
for (int i = 0; i < length; i++) {
key[i] = solvePosition(i, messages);
}
return key;
}
private byte solvePosition(int pos, byte[][] messages) {
int[] keyGuessCount = new int[256];
int totalKeyGuess = 0;
for (int i = 0; i < messages.length - SPACE_TEST_NUM; i++) {
int success = 0;
for (int j = 0; j < SPACE_TEST_NUM; j++) {
if (((messages[i][pos] ^ messages[i + j][pos]) & ' ') != 0) {
success++;
}
}
if (success >= SPACE_TEST_MIN) {
int keyGuess = (messages[i][pos] ^ ' ') & 0xFF;
keyGuessCount[keyGuess]++;
totalKeyGuess++;
if (keyGuessCount[keyGuess] >= KEY_GUESS_MIN && keyGuessCount[keyGuess] > totalKeyGuess *
KEY_GUESS_MIN_PERCENTAGE) {
System.out.println("Found " + pos + " using " + (i + 1 + SPACE_TEST_NUM) + " messages");
return (byte) keyGuess;
}
}
}
throw new IllegalArgumentException("Too few messages");
}
}
关于java - 仅通过知道异或加密的字节数组和 key 大小来获取 key 字符串，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26525868/