只知道密钥长度才中断Vigenere

问题描述 投票:1回答:1

问题

我想解码使用经典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);
    }
}
java decode vigenere
1个回答
0
投票

非文本消息

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

尤其是文本实际上是经过哈希处理或双重加密,即“随机内容”。

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


先决条件

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

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

MYNAMEISJOHN // Instead of: My name is John.

同样也适用于您的密钥,它只包含AZ

然后,经典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

Letter frequency

[您现在要做的就是将消息分割成多个块(键长度为模,并对每个块的位数进行频率分析。

因此,对于您的特定输入,这将产生块

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); } } }

© www.soinside.com 2019 - 2024. All rights reserved.