我想解码使用经典Viginere加密的消息。我知道key的长度恰好是6个字符。
消息是:
BYOIZRLAUMYXXPFLPWBZLMLQPBJMSCQOWVOIJPYPALXCWZLKXYVMKXEHLIILLYJMUGBVXBOIRUAVAEZAKBHXBDZQJLELZIKMKOWZPXBKOQALQOWKYIBKGNTCPAAKPWJHKIAPBHKBVTBULWJSOYWKAMLUOPLRQOWZLWRSLEHWABWBVXOLSKOIOFSZLQLYKMZXOBUSPRQVZQTXELOWYHPVXQGDEBWBARBCWZXYFAWAAMISWLPREPKULQLYQKHQBISKRXLOAUOIEHVIZOBKAHGMCZZMSSSLVPPQXUVAOIEHVZLTIPWLPRQOWIMJFYEIAMSLVQKWELDWCIEPEUVVBAZIUXBZKLPHKVKPLLXKJMWPFLVBLWPDGCSHIHQLVAKOWZSMCLXWYLFTSVKWELZMYWBSXKVYIKVWUSJVJMOIQOGCNLQVXBLWPHKAOIEHVIWTBHJMKSKAZMKEVVXBOITLVLPRDOGEOIOLQMZLXKDQUKBYWLBTLUZQTLLDKPLLXKZCUKRWGVOMPDGZKWXZANALBFOMYIXNGLZEKKVCYMKNLPLXBYJQIPBLNMUMKNGDLVQOWPLEOAZEOIKOWZZMJWDMZSRSMVJSSLJMKMQZWTMXLOAAOSTWABPJRSZMYJXJWPHHIVGSLHYFLPLVXFKWMXELXQYIFUZMYMKHTQSMQFLWYIXSAHLXEHLPPWIVNMHRAWJWAIZAAWUGLBDLWSPZAJSCYLOQALAYSEUXEBKNYSJIWQUKELJKYMQPUPLKOLOBVFBOWZHHSVUIAIZFFQJEIAZQUKPOWPHHRALMYIAAGPPQPLDNHFLBLPLVYBLVVQXUUIUFBHDEHCPHUGUM
我尝试过蛮力的方法,但不幸的是,这样产生的组合数量非常多,无法计算。
您是否知道如何从这里出发或通常如何解决此问题?
这是我到目前为止的内容:
public class Main {
// instance variables - replace the example below with your own
private String message;
private String answer;
private String first;
/**
* Constructor for objects of class Main
*/
public Main()
{
// initialise instance variables
message ="BYOIZRLAUMYXXPFLPWBZLMLQPBJMSCQOWVOIJPYPALXCWZLKXYVMKXEHLIILLYJMUGBVXBOIRUAVAEZAKBHXBDZQJLELZIKMKOWZPXBKOQALQOWKYIBKGNTCPAAKPWJHKIAPBHKBVTBULWJSOYWKAMLUOPLRQOWZLWRSLEHWABWBVXOLSKOIOFSZLQLYKMZXOBUSPRQVZQTXELOWYHPVXQGDEBWBARBCWZXYFAWAAMISWLPREPKULQLYQKHQBISKRXLOAUOIEHVIZOBKAHGMCZZMSSSLVPPQXUVAOIEHVZLTIPWLPRQOWIMJFYEIAMSLVQKWELDWCIEPEUVVBAZIUXBZKLPHKVKPLLXKJMWPFLVBLWPDGCSHIHQLVAKOWZSMCLXWYLFTSVKWELZMYWBSXKVYIKVWUSJVJMOIQOGCNLQVXBLWPHKAOIEHVIWTBHJMKSKAZMKEVVXBOITLVLPRDOGEOIOLQMZLXKDQUKBYWLBTLUZQTLLDKPLLXKZCUKRWGVOMPDGZKWXZANALBFOMYIXNGLZEKKVCYMKNLPLXBYJQIPBLNMUMKNGDLVQOWPLEOAZEOIKOWZZMJWDMZSRSMVJSSLJMKMQZWTMXLOAAOSTWABPJRSZMYJXJWPHHIVGSLHYFLPLVXFKWMXELXQYIFUZMYMKHTQSMQFLWYIXSAHLXEHLPPWIVNMHRAWJWAIZAAWUGLBDLWSPZAJSCYLOQALAYSEUXEBKNYSJIWQUKELJKYMQPUPLKOLOBVFBOWZHHSVUIAIZFFQJEIAZQUKPOWPHHRALMYIAAGPPQPLDNHFLBLPLVYBLVVQXUUIUFBHDEHCPHUGUM";
for (int x = 0; x < message.length() / 6; x++) {
int index = x * 6;
first = new StringBuilder()
.append(first)
.append(message.charAt(index))
.toString();
}
System.out.println(first);
}
}
如果原始消息不是真实的文本(例如有意义的英语文本),或者您没有有关其内容的信息,那么您将很不走运。
尤其是文本实际上是经过哈希处理或双重加密,即“随机内容”。
破坏加密方案需要有关算法和消息的知识。特别是在您遇到的情况下,您需要了解消息的一般结构才能破解它。
对于此答案的其余部分,让我假设您的信息实际上是纯英文文本。请注意,您可以轻松采用我对其他语言的回答。甚至采用其他消息格式的技术。
让我也假设您是在谈论经典的Vigenere(请参阅Wikipedia),而不是其众多变体之一。这意味着您的输入仅由字母A
至Z
组成,没有大小写,没有句号,没有空格。示例:
MYNAMEISJOHN // Instead of: My name is John.
同样也适用于您的密钥,它只包含A
至Z
。
然后,经典Viginere以字母的偏移量为偏移量,以字母大小为模(26
)。
示例:
(G + L) % 26 = R
在讨论攻击之前,我们需要找到一种方法,给定生成的密钥,以找出它是否正确。
由于我们知道消息是由英文文本组成的,因此我们可以仅使用字典(所有有效英语单词的巨大列表),然后将解密后的消息与字典进行比较。如果密钥错误,那么生成的消息将不包含有效词(或仅包含少量词)。
这可能有点棘手,因为我们没有插句法(特别是没有空格)。
很好的是,实际上有一种非常准确的方法来测量文本的[[valid程度,这也解决了缺少插入点的问题。
该技术称为N-gram(请参见Wikipedia)。您为N
选择一个值,例如3
(然后称为tri-grams),然后开始将文本分成3个字符对。示例:
MYNAMEISJOHN // results in the trigrams:
$$M, $$MY, MYN, YNA, NAM, AME, MEI, ISJ, SJO, JOH, OHN, HN$, N$$
您现在需要的是对英文文本中最常见的三字组进行频率分析。在线上有各种资源(或者您可以自己在大型文本语料库上运行它。)>您可以通过在最高发行版中尝试几种组合来解决这一问题。因此,对于第一位数,您可以尝试是否然后,您只需将三元语法的频率与真实文本的频率进行比较。使用它,您可以计算出您的频率与实际频率的匹配程度得分。如果您的消息包含很多非常不常见的三字母组,则很可能是垃圾数据,而不是真实文本。
一个小注释,字母组合(1克)产生一个字符频率(请参见Wikipedia#Letter frequency)。 Bi-gram(2-gram)通常用于裂解Viginere,并产生良好的结果。
攻击蛮力
第一个也是最直接的攻击总是蛮力。而且,只要键和字母没有那么大,组合的数量就相对较低。
您的键的长度为
6
,字母的大小为26
。因此,不同组合键的数量为6^26
,即[]
170_581_728_179_578_208_256
关于10^20
。这个数字可能看起来很大,但不要忘记,CPU已经在千兆赫范围内运行(每个内核每秒10^9
操作)。这意味着一个拥有1 GHz频率的单核将在大约317年内产生所有解决方案。现在,用功能强大的CPU(甚至GPU)和多核计算机(存在具有数百万个核的群集)代替它,然后就可以在不到一天的时间内进行计算。但是好吧,我知道您很可能无权访问这样的核心集群。因此,完全的暴力破解是不可行的。
但请放心。有一些简单的技巧可以加快速度。您不必计算完整密钥。如何将自己限制在前3个字符而不是完整的6个字符。然后,您将只能解密文本的一个子集,但是足以分析结果是否为有效文本(如前所述,使用字典和N-gram)。
这个小小的改变已经大大减少了计算时间,因为那时您只有
3^26
组合。对于单个1 GHz内核,生成这些文件大约需要2分钟。但是您可以做更多。某些字符在英语文本中极为罕见,例如
Z
。您可以从不考虑将转换为文本中的那些值的键开始。假设您删除了这6个最不常用的字符,那么您的组合仅为3^20
。对于单个1 GHz内核,这大约需要100毫秒。是的,毫秒。对于普通笔记本电脑来说,这足够快。频率攻击
足够的蛮力,让我们做一些聪明的事情。字母频率攻击是针对那些加密方案的非常常见的攻击。它简单,快速且非常成功。实际上,它是如此简单,以至于有很多在线工具免费提供此功能,例如guballa.de/vigenere-solver(它可以破解您的特定示例,我刚刚尝试过)。
虽然Viginere将消息更改为不可读的垃圾,但是它不会更改字母的分布,至少不会更改密钥的每个数字。因此,如果您查看,假设您输入了密钥的第二个数字,则消息中的每个第二个字母将偏移完全相同的偏移量。
让我们看一个简单的例子。关键是
BAC
,消息是
CCC CCC CCC CCC CCC // raw DCF DCF DCF DCF DCF // decrypted
您注意到,字母重复。查看第三个字母,它始终是F
。因此,这意味着第六和第九个字母(也都是F
)都必须是完全相同的原始字母。因为它们都从键上移了C
。这是非常重要的观察。这表示字母频率在键(
k * (i + key_length)
)的数字的整数倍内被保留。现在让我们看一下英文文本中的字母分布(来自Wikipedia:
[您现在要做的就是将消息分割成多个块(键长度为模,并对每个块的位数进行频率分析。
因此,对于您的特定输入,这将产生块
BYOIZR LAUMYX XPFLPW BZLMLQ PBJMSC ...
现在,您将分析每个块的数字1
,然后是数字2
,依此类推,直到数字6
。对于第一个数字,这是字母B,L,X,B,P,...
您的特定输入的结果是:
[B=0.150, E=0.107, X=0.093, L=0.079, Q=0.079, P=0.071, K=0.064, I=0.050, O=0.050, R=0.043, F=0.036, J=0.036, A=0.029, S=0.029, Y=0.021, Z=0.021, C=0.014, T=0.014, D=0.007, V=0.007] [L=0.129, O=0.100, H=0.093, A=0.079, V=0.071, Y=0.071, B=0.057, K=0.057, U=0.050, F=0.043, P=0.043, S=0.043, Z=0.043, D=0.029, W=0.029, N=0.021, C=0.014, I=0.014, J=0.007, T=0.007] [W=0.157, Z=0.093, K=0.079, L=0.079, V=0.079, A=0.071, G=0.071, J=0.064, O=0.050, X=0.050, D=0.043, U=0.043, S=0.036, Q=0.021, E=0.014, F=0.014, N=0.014, M=0.007, T=0.007, Y=0.007] [M=0.150, P=0.100, Q=0.100, I=0.079, B=0.071, Z=0.071, L=0.064, W=0.064, K=0.057, V=0.043, E=0.036, A=0.029, C=0.029, N=0.029, U=0.021, H=0.014, S=0.014, D=0.007, G=0.007, J=0.007, T=0.007] [L=0.136, Y=0.100, A=0.086, O=0.086, P=0.086, U=0.086, H=0.064, K=0.057, V=0.050, Z=0.050, S=0.043, J=0.029, M=0.021, T=0.021, W=0.021, G=0.014, I=0.014, B=0.007, C=0.007, N=0.007, R=0.007, X=0.007] [I=0.129, M=0.107, X=0.100, L=0.086, W=0.079, S=0.064, R=0.057, H=0.050, Q=0.050, K=0.043, E=0.036, C=0.029, T=0.029, V=0.029, F=0.021, J=0.021, P=0.021, G=0.014, Y=0.014, A=0.007, D=0.007, O=0.007]
看看。您会看到,对于第一个数字,字母获得的B
很常见,即15%
。然后在E
上加上10%
,以此类推。密钥的第一个字母B
很可能是真实文本中E
的别名(因为E
是英文文本中最常见的字母),并且E
代表第二个最常见的字母,即T
。使用您可以轻松地反向计算用于加密的密钥字母。它是通过
B - E % 26 = X
请注意,您的消息分发可能不必与所有英文文本的实际分发保持一致。特别是如果消息不是那么长(分布计算的时间越长,则越准确)或主要由单词组成。weird
和unusual
B -> E
E -> E
X -> E
L -> E
或者不尝试仅映射到E
,也请尝试第二个最常见的字符T
:
B -> T E -> T X -> T L -> T
您获得的组合数量很少。使用字典和N-gram(如前所述)验证密钥是否正确。Java实现
因为它是如此简单和琐碎,下面是我逐步解释的Java的完整实现,并提供了一些调试输出:
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public final class CrackViginere {
private static final int ALPHABET_SIZE = 26;
private static final char FIRST_CHAR_IN_ALPHABET = 'A';
public static void main(final String[] args) {
String encrypted =
"BYOIZRLAUMYXXPFLPWBZLMLQPBJMSCQOWVOIJPYPALXCWZLKXYVMKXEHLIILLYJMUGBVXBOIRUAVAEZAKBHXBDZQJLELZIKMKOWZPXBKOQALQOWKYIBKGNTCPAAKPWJHKIAPBHKBVTBULWJSOYWKAMLUOPLRQOWZLWRSLEHWABWBVXOLSKOIOFSZLQLYKMZXOBUSPRQVZQTXELOWYHPVXQGDEBWBARBCWZXYFAWAAMISWLPREPKULQLYQKHQBISKRXLOAUOIEHVIZOBKAHGMCZZMSSSLVPPQXUVAOIEHVZLTIPWLPRQOWIMJFYEIAMSLVQKWELDWCIEPEUVVBAZIUXBZKLPHKVKPLLXKJMWPFLVBLWPDGCSHIHQLVAKOWZSMCLXWYLFTSVKWELZMYWBSXKVYIKVWUSJVJMOIQOGCNLQVXBLWPHKAOIEHVIWTBHJMKSKAZMKEVVXBOITLVLPRDOGEOIOLQMZLXKDQUKBYWLBTLUZQTLLDKPLLXKZCUKRWGVOMPDGZKWXZANALBFOMYIXNGLZEKKVCYMKNLPLXBYJQIPBLNMUMKNGDLVQOWPLEOAZEOIKOWZZMJWDMZSRSMVJSSLJMKMQZWTMXLOAAOSTWABPJRSZMYJXJWPHHIVGSLHYFLPLVXFKWMXELXQYIFUZMYMKHTQSMQFLWYIXSAHLXEHLPPWIVNMHRAWJWAIZAAWUGLBDLWSPZAJSCYLOQALAYSEUXEBKNYSJIWQUKELJKYMQPUPLKOLOBVFBOWZHHSVUIAIZFFQJEIAZQUKPOWPHHRALMYIAAGPPQPLDNHFLBLPLVYBLVVQXUUIUFBHDEHCPHUGUM";
int keyLength = 6;
char mostCommonCharOverall = 'E';
// Blocks
List<String> blocks = new ArrayList<>();
for (int startIndex = 0; startIndex < encrypted.length(); startIndex += keyLength) {
int endIndex = Math.min(startIndex + keyLength, encrypted.length());
String block = encrypted.substring(startIndex, endIndex);
blocks.add(block);
}
System.out.println("Individual blocks are:");
blocks.forEach(System.out::println);
// Frequency
List<Map<Character, Integer>> digitToCounts = Stream.generate(HashMap<Character, Integer>::new)
.limit(keyLength)
.collect(Collectors.toList());
for (String block : blocks) {
for (int i = 0; i < block.length(); i++) {
char c = block.charAt(i);
Map<Character, Integer> counts = digitToCounts.get(i);
counts.compute(c, (character, count) -> count == null ? 1 : count + 1);
}
}
List<List<CharacterFrequency>> digitToFrequencies = new ArrayList<>();
for (Map<Character, Integer> counts : digitToCounts) {
int totalCharacterCount = counts.values()
.stream()
.mapToInt(Integer::intValue)
.sum();
List<CharacterFrequency> frequencies = new ArrayList<>();
for (Map.Entry<Character, Integer> entry : counts.entrySet()) {
double frequency = entry.getValue() / (double) totalCharacterCount;
frequencies.add(new CharacterFrequency(entry.getKey(), frequency));
}
Collections.sort(frequencies);
digitToFrequencies.add(frequencies);
}
System.out.println("Frequency distribution for each digit is:");
digitToFrequencies.forEach(System.out::println);
// Guessing
StringBuilder keyBuilder = new StringBuilder();
for (List<CharacterFrequency> frequencies : digitToFrequencies) {
char mostFrequentChar = frequencies.get(0)
.getCharacter();
int keyInt = mostFrequentChar - mostCommonCharOverall;
keyInt = keyInt >= 0 ? keyInt : keyInt + ALPHABET_SIZE;
char key = (char) (FIRST_CHAR_IN_ALPHABET + keyInt);
keyBuilder.append(key);
}
String key = keyBuilder.toString();
System.out.println("The guessed key is: " + key);
System.out.println("Decrypted message:");
System.out.println(decrypt(encrypted, key));
}
private static String decrypt(String encryptedMessage, String key) {
StringBuilder decryptBuilder = new StringBuilder(encryptedMessage.length());
int digit = 0;
for (char encryptedChar : encryptedMessage.toCharArray())
{
char keyForDigit = key.charAt(digit);
int decryptedCharInt = encryptedChar - keyForDigit;
decryptedCharInt = decryptedCharInt >= 0 ? decryptedCharInt : decryptedCharInt + ALPHABET_SIZE;
char decryptedChar = (char) (decryptedCharInt + FIRST_CHAR_IN_ALPHABET);
decryptBuilder.append(decryptedChar);
digit = (digit + 1) % key.length();
}
return decryptBuilder.toString();
}
private static class CharacterFrequency implements Comparable<CharacterFrequency> {
private final char character;
private final double frequency;
private CharacterFrequency(final char character, final double frequency) {
this.character = character;
this.frequency = frequency;
}
@Override
public int compareTo(final CharacterFrequency o) {
return -1 * Double.compare(frequency, o.frequency);
}
private char getCharacter() {
return character;
}
private double getFrequency() {
return frequency;
}
@Override
public String toString() {
return character + "=" + String.format("%.3f", frequency);
}
}
}