问题
我想解码使用经典Viginere加密的消息。我知道键的长度正好是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
字典
在讨论攻击之前，我们需要找到一种方法，给定生成的密钥，找出它是否正确。
因为我们知道消息是由英文文本组成的，所以我们只需拿字典（所有有效英语单词的巨大列表），然后将解密后的消息与字典进行比较。如果密钥输入错误，则生成的消息将不包含有效词（或仅包含几个词）。
这可能有点棘手，因为我们缺少插入点（特别是没有空格）。
克
幸运的是，实际上有一种非常准确的方法来衡量文本的有效性，这也解决了缺少插入点的问题。
该技术称为N-gram（请参见Wikipedia）。您为
N选择一个值，例如3（然后称为三字母组），然后开始将文本分成3个字符对。例：MYNAMEISJOHN // results in the trigrams:
$$M, $$MY, MYN, YNA, NAM, AME, MEI, ISJ, SJO, JOH, OHN, HN$, N$$
您现在需要的是对英语文本中最常见的三字组进行频率分析。在线上有各种资源（或者您可以自己在大型文本语料库上运行它）。
然后，您只需将三元语法的频率与真实文本的频率进行比较。使用它，您可以计算出您的频率与实际频率的匹配程度得分。如果您的消息包含很多非常不常见的三字母组，则很可能是垃圾数据，而不是真实文本。
小写的字母组合表示法（1-gram）产生单个字符频率（请参见Wikipedia#Letter frequency）。 Bi-gram（2-gram）通常用于裂解Viginere，并产生良好的结果。
进攻
蛮力
第一个也是最直接的攻击始终是蛮力攻击。并且，只要键和字母不那么大，组合的数量就相对较低。
您的密钥的长度为
6，字母的大小为26。因此，不同组合键的数量为6^26，即170_581_728_179_578_208_256
关于
10^20。这个数字可能看起来很大，但不要忘记，CPU已经在千兆赫范围内运行（每个内核每秒10^9操作）。这意味着在大约317年的时间里，具有1 GHz的单个内核将产生所有解决方案。现在，用功能强大的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
请注意，您的消息分发可能不必与所有英文文本的实际分发保持一致。特别是如果消息不是那么长（分布计算越长，则越准确）或主要由怪异的单词组成。
您可以通过在最高发行版中尝试几种组合来解决这一问题。所以对于第一个数字，您可以尝试
B -> E
E -> E
X -> E
L -> E
或者，也可以尝试使用第二个最常见的字符
E，而不是仅映射到T：B -> T
E -> T
X -> T
L -> T
您获得的组合数量很少。使用字典和N-gram（如前所述）来验证密钥是否正确。
Java实现
您的信息实际上非常有趣。它与英文文本上的真实字母频率完全吻合。因此，对于您的特殊情况，您实际上不需要尝试任何组合，也不需要进行任何字典/ n-gram检查。实际上，您可以将加密消息中最常见的字母（按数字）转换为英文文本中最常见的字符
E，并获得真实的实际密钥。因为这是如此简单和琐碎，所以下面是我逐步解释的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);
}
}
}
已解密
使用上面的代码，关键是：
XHSIHE
完整的解密消息为：
ERWASNOTCERTAINDISESTEEMSURELYTHENHEMIGHTHAVEREGARDEDTHATABHORRENCEOFTHEUNINTACTSTATEWHICHHEHADINHERITEDWITHTHECREEDOFMYSTICISMASATLEASTOPENTOCORRECTIONWHENTHERESULTWASDUETOTREACHERYAREMORSESTRUCKINTOHIMTHEWORDSOFIZZHUETTNEVERQUITESTILLEDINHISMEMORYCAMEBACKTOHIMHEHADASKEDIZZIFSHELOVEDHIMANDSHEHADREPLIEDINTHEAFFIRMATIVEDIDSHELOVEHIMMORETHANTESSDIDNOSHEHADREPLIEDTESSWOULDLAYDOWNHERLIFEFORHIMANDSHEHERSELFCOULDDONOMOREHETHOUGHTOFTESSASSHEHADAPPEAREDONTHEDAYOFTHEWEDDINGHOWHEREYESHADLINGEREDUPONHIMHOWSHEHADHUNGUPONHISWORDSASIFTHEYWEREAGODSANDDURINGTHETERRIBLEEVENINGOVERTHEHEARTHWHENHERSIMPLESOULUNCOVEREDITSELFTOHISHOWPITIFULHERFACEHADLOOKEDBYTHERAYSOFTHEFIREINHERINABILITYTOREALIZETHATHISLOVEANDPROTECTIONCOULDPOSSIBLYBEWITHDRAWNTHUSFROMBEINGHERCRITICHEGREWTOBEHERADVOCATECYNICALTHINGSHEHADUTTEREDTOHIMSELFABOUTHERBUTNOMANCANBEALWAYSACYNI
或多或少是有效的英文文本：
er was not certain disesteem surely then he might have regarded that
abhorrence of the unintact state which he had inherited with the creed
of my sticismas at least open to correction when the result was due to
treachery are morse struck into him the words of izz huett never quite
still ed in his memory came back to him he had asked izz if she loved
him and she had replied in the affirmative did she love him more than
tess did no she had replied tess would lay down her life for him and she
herself could do no more he thought of tess as she had appeared on the day
of the wedding how here yes had lingered upon him how she had hung upon
his words as if they were a gods and during the terrible evening over
the hearth when her simple soul uncovered itself to his how pitiful her
face had looked by the rays of the fire inherinability to realize that
his love and protection could possibly be withdrawn thus from being her
critiche grew to be her advocate cynical things he had uttered to
himself about her but noman can be always acyn I
顺便说一句，这是英国小说Tess of the d'Urbervilles: A Pure Woman Faithfully Presented的一句话。第六阶段：转换，第XLIX章。
关于java - 只知道 key 长度才能破解Vigenere，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/59094006/