破解仅知道密钥长度的 Vigenere
Breaking Vigenere only knowing key length
问题
我想解码一条用经典 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);
}
}
非短信
如果原始消息不是实际文本（比如有意义的英文文本），或者您没有关于其内容的信息，那您就不走运了。
特别是如果文本实际上是散列的或双重加密的，即 随机的东西。
破解加密方案需要了解算法和消息。特别是在您的情况下，您需要了解消息的一般结构才能破解它。
先决条件
对于这个答案的其余部分，让我假设您的消息实际上是纯英文文本。请注意，您可以轻松采用我对其他语言的回答。甚至将这些技术应用于其他消息格式。
我还假设您谈论的是经典维吉尼亚葡萄酒（参见 Wikipedia），而不是它的众多变体之一。这意味着您的输入仅包含字母 A 到 Z，没有大小写，没有句号，没有空格。示例：
MYNAMEISJOHN // Instead of: My name is John.
同样适用于你的密钥，它只包含A到Z。
Classic Viginere 然后移动字母表中的偏移量，以字母表大小为模（即 26）。
示例：
(G + L) % 26 = R
词典
在我们讨论攻击之前，我们需要找到一种方法，根据生成的密钥，找出它是否真的正确。
因为我们知道消息由英文文本组成，我们可以只拿一本字典（所有有效英文单词的巨大列表）并将我们解密的消息与字典进行比较。如果密钥错误，生成的消息将不包含有效单词（或只有几个）。
这可能有点棘手，因为我们缺少标点符号（特别是没有空格）。
N-grams
幸好实际上有一种非常准确的方法可以衡量文本的有效性，这也解决了缺少标点符号的问题。
该技术称为 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-gram）导致单个字符频率（参见Wikipedia#Letter frequency）。 Bi-grams (2-gram) 通常用于破解 Viginere 并产生良好的结果。
攻击
蛮力
第一个也是最直接的攻击总是蛮力攻击。而且，只要键和字母不是那么大，组合的数量就比较少。
您的密钥长度为 6，字母表的长度为 26。所以不同组合键的数量是6^26，也就是
170_581_728_179_578_208_256
所以大约 10^20。这个数字可能看起来很大，但不要忘记 CPUs 已经在千兆赫兹范围内运行（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
请注意，您的消息分布可能不需要与所有英文文本的实际分布保持一致。特别是如果消息不是那么长（越长，分布计算越准确）或者主要由怪异和不寻常字组成。
您可以通过在最高分布中尝试一些组合来解决这个问题。所以对于第一个数字，你可以试试是否
B -> E
E -> E
X -> E
L -> E
或者不只映射到 E，还尝试第二个最常见的字符 T:
B -> T
E -> T
X -> T
L -> T
你得到的组合数量非常少。使用字典和 N-gram（如前所述）来验证密钥是否正确。
Java 实施
你的留言其实很有意思。它与英文文本上的真实字母频率完美对齐。因此，对于您的特定情况，您实际上不需要尝试任何组合，也不需要进行任何 dictionary/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。 第六阶段：皈依，第四十九章。
标准 Vigenere 交错凯撒移位密码，由密钥指定。如果 Vigenere 密钥的长度为六个字符，则密文的字母 1、7、13 ... 是一次凯撒移位——每六个字符使用密钥的第一个字符。密文的字母 2、8、14 ... 使用不同的（通常）凯撒移位等。
这给了你六种不同的凯撒移位密码来解决。文本不会是英文的，因为每六个字母都要挑一次，所以你需要通过字母频率来解决它。这将为您提供键的每个位置的几个不错的选择。按概率顺序尝试它们，看看哪个给出正确的解密。
问题
我想解码一条用经典 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);
}
}
非短信
如果原始消息不是实际文本（比如有意义的英文文本），或者您没有关于其内容的信息，那您就不走运了。
特别是如果文本实际上是散列的或双重加密的，即 随机的东西。
破解加密方案需要了解算法和消息。特别是在您的情况下，您需要了解消息的一般结构才能破解它。
先决条件
对于这个答案的其余部分，让我假设您的消息实际上是纯英文文本。请注意，您可以轻松采用我对其他语言的回答。甚至将这些技术应用于其他消息格式。
我还假设您谈论的是经典维吉尼亚葡萄酒（参见 Wikipedia），而不是它的众多变体之一。这意味着您的输入仅包含字母 A 到 Z，没有大小写，没有句号，没有空格。示例：
MYNAMEISJOHN // Instead of: My name is John.
同样适用于你的密钥，它只包含A到Z。
Classic Viginere 然后移动字母表中的偏移量，以字母表大小为模（即 26）。
示例：
(G + L) % 26 = R
词典
在我们讨论攻击之前，我们需要找到一种方法，根据生成的密钥，找出它是否真的正确。
因为我们知道消息由英文文本组成，我们可以只拿一本字典（所有有效英文单词的巨大列表）并将我们解密的消息与字典进行比较。如果密钥错误，生成的消息将不包含有效单词（或只有几个）。
这可能有点棘手，因为我们缺少标点符号（特别是没有空格）。
N-grams
幸好实际上有一种非常准确的方法可以衡量文本的有效性，这也解决了缺少标点符号的问题。
该技术称为 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-gram）导致单个字符频率（参见Wikipedia#Letter frequency）。 Bi-grams (2-gram) 通常用于破解 Viginere 并产生良好的结果。
攻击
蛮力
第一个也是最直接的攻击总是蛮力攻击。而且，只要键和字母不是那么大，组合的数量就比较少。
您的密钥长度为 6，字母表的长度为 26。所以不同组合键的数量是6^26，也就是
170_581_728_179_578_208_256
所以大约 10^20。这个数字可能看起来很大，但不要忘记 CPUs 已经在千兆赫兹范围内运行（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
请注意，您的消息分布可能不需要与所有英文文本的实际分布保持一致。特别是如果消息不是那么长（越长，分布计算越准确）或者主要由怪异和不寻常字组成。
您可以通过在最高分布中尝试一些组合来解决这个问题。所以对于第一个数字，你可以试试是否
B -> E
E -> E
X -> E
L -> E
或者不只映射到 E，还尝试第二个最常见的字符 T:
B -> T
E -> T
X -> T
L -> T
你得到的组合数量非常少。使用字典和 N-gram（如前所述）来验证密钥是否正确。
Java 实施
你的留言其实很有意思。它与英文文本上的真实字母频率完美对齐。因此，对于您的特定情况，您实际上不需要尝试任何组合，也不需要进行任何 dictionary/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。 第六阶段：皈依，第四十九章。
标准 Vigenere 交错凯撒移位密码，由密钥指定。如果 Vigenere 密钥的长度为六个字符，则密文的字母 1、7、13 ... 是一次凯撒移位——每六个字符使用密钥的第一个字符。密文的字母 2、8、14 ... 使用不同的（通常）凯撒移位等。
这给了你六种不同的凯撒移位密码来解决。文本不会是英文的，因为每六个字母都要挑一次，所以你需要通过字母频率来解决它。这将为您提供键的每个位置的几个不错的选择。按概率顺序尝试它们，看看哪个给出正确的解密。