只知道密钥长度才中断Vigenere

Question

问题

我想解码使用经典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);
    }
}

Answer 1

非文本消息

如果原始消息不是真实的文本（例如有意义的英语文本），或者您没有有关其内容的信息，那么您将很不走运。

特别是文本实际上是经过哈希处理还是双重加密，即随机内容。

破坏加密方案需要有关算法和消息的知识。特别是在您遇到的情况下，您需要了解消息的一般结构才能破解它。

---

先决条件

对于此答案的其余部分，让我假设您的信息实际上是纯英文文本。请注意，您可以轻松采用我对其他语言的回答。甚至采用其他消息格式的技术。

让我也假设您是在谈论经典的Vigenere（请参阅Wikipedia），而不是其众多变体之一。这意味着您的输入仅由字母A至Z组成，没有大小写，没有句号，没有空格。示例：

MYNAMEISJOHN // Instead of: My name is John.

同样也适用于您的密钥，它只包含A至Z。

然后，经典Viginere以字母的偏移量为偏移量，以字母大小为模（26）。

示例：

(G + L) % 26 = R

---

字典

在讨论攻击之前，我们需要找到一种方法，给定生成的密钥，以找出它是否正确。

由于我们知道消息是由英文文本组成的，因此我们可以仅使用字典（所有有效英语单词的巨大列表），然后将解密后的消息与字典进行比较。如果密钥错误，那么生成的消息将不包含有效词（或仅包含少量词）。

这可能有点棘手，因为我们没有插句法（特别是没有空格）。

N-克

很好的是，实际上有一种非常准确的方法来测量文本的[[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实现

您的信息实际上非常有趣。它与英文文本的真实字母频率完全吻合。因此，对于您的特定情况，您实际上不需要尝试任何组合，也不需要进行任何字典/ 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章
。

标准Vigenere交织凯撒移位密码，由密钥指定。如果Vigenere密钥的长度为6个字符，则密文的字母1、7、13 ...处于一个凯撒移位状态-每六个字符使用密钥的第一个字符。密文的字母2、8、14 ...使用不同的（通常是）凯撒移位，依此类推。

这为您提供了六个不同的Caesar移位密码来解决。由于选择的是第六个字母，因此该文本将不是英语，因此您需要按字母频率来解决。这样可以为钥匙的每个位置提供一些不错的选择。以概率的顺序尝试一下，看看能给出正确的解密。

Answer 2

标准Vigenere交织凯撒移位密码，由密钥指定。如果Vigenere密钥的长度为6个字符，则密文的字母1、7、13 ...处于一个凯撒移位状态-每六个字符使用密钥的第一个字符。密文的字母2、8、14 ...使用不同的（通常是）凯撒移位，依此类推。