如何决定所选密码是否正确?

正如您所建议的,人们希望明文具有某种已知格式,例如,一个jpeg图像、一个pdf文件等。其想法是,给定的密文不太可能同时解密为有效的jpeg图像和一个有效的pdf文件(见下文)。

但实际上并不那么重要。当我们谈到密码系统 保护 一个(粗略地)谈论你能够猜出与给定密文相对应的明文的几率。所以我选择了一条随机信息 米 并加密它 C = e ( 米 )我给你 C 如果你猜不到 米 然后我们说密码系统是安全的,否则它就坏了。

这只是一个简单的安全定义。还有其他定义要求系统能够 hide known plaintexts (语义安全):您给我两条消息,我加密其中一条,您将无法知道我选择了哪条消息。

关键是,在这些定义中,我们不关心明文的格式,我们所需要的只是您不能猜测加密的明文。 所以没有步骤3:-)

通过不考虑第3步,我们尽可能清楚地提出了安全问题:我们不讨论猜测您使用哪种格式(zip、gzip、bzip2,…)有多困难,而只讨论与猜测 钥匙 . 这是一个 old principle 您应该将所有的安全性集中在密钥中——当您唯一的假设是密钥的保密性时,它会显著地简化事情。

最后,请注意,由于所有密钥都是合法的,因此某些加密方案使您无法验证您是否拥有正确的密钥。这个 one-time pad 就是这样一个极端的例子:你拿你的纯文本 米 ,选择一个完全随机的键 K 把密文计算为 C = 米 异或 K . 这给你一个完全随机的密文,它是完全安全的(唯一完全安全的密码系统,btw)。

在搜索加密密钥时,您不知道何时找到了正确的密钥。这是因为 C 可以是任何文件的加密,其长度与 米 :如果加密邮件 M’ 用键“K”= C 异或 M’ 你会发现你又得到了同样的密文,因此你不知道 米 或 M’ 是原始消息。

你可以把一次性的pad想象成这样:我给你42,告诉你这是两个整数的和(负的,正的,你不知道)。一个整数是消息,另一个是密钥,42是密文。像上面所说的,猜测这个键是没有意义的——如果你想让消息是100,你就说这个键是-58,如果你想让消息是0,你就说这个键是42,等等。一个记事本的工作原理和这个完全一样,但是在位值上。

关于在一次性PAD中重用密钥: 假设我的钥匙是7,你会看到密文10和20,对应于明文3和13。仅从密文中,你就知道明文的差别是10。如果你以某种方式获得了明文中的一个的知识,你现在就可以得到另一个了!如果数字与单个字母相对应,您可以开始查看几个这样的差异,并尝试解决由此产生的纵横字谜(或让程序基于所讨论语言的频率分析来完成)。

您可以使用类似于Unix的启发式方法

file

命令会检查已知的文件类型。如果您已经解密了没有可识别类型的数据,那么解密它无论如何都不会帮助您,因为您无法解释它,所以它仍然和加密一样好。

不久前我编写了一个工具,它通过简单检查字节值的分布来检查文件是否可能被加密,因为加密的文件应该与随机噪声不可区分。这里的假设是,不正确解密的文件保留随机性,而正确解密的文件将显示结构。

#!/usr/bin/env python

import math
import sys
import os

MAGIC_COEFF=3

def get_random_bytes(filename):
        BLOCK_SIZE=1024*1024
        BLOCKS=10

        f=open(filename)
        bytes=list(f.read(BLOCK_SIZE))

        if len(bytes) < BLOCK_SIZE:
                return bytes

        f.seek(0, 2)
        file_len = f.tell()
        index = BLOCK_SIZE
        cnt=0
        while index < file_len and cnt < BLOCKS:
                f.seek(index)
                more_bytes = f.read(BLOCK_SIZE)
                bytes.extend(more_bytes)
                index+=ord(os.urandom(1))*BLOCK_SIZE
                cnt+=1

        return bytes

def failed_n_gram(n,bytes):
        print "\t%d-gram analysis"%(n)
        N = len(bytes)/n
        states = 2**(8*n)
        print "\tN: %d states: %d"%(N, states)

        if N < states:
                print "\tinsufficient data"
                return False

        histo = [0]*states
        P = 1.0/states

        expected = N/states * 1.0
        # I forgot how this was derived, or what it is suppose to be
        magic = math.sqrt(N*P*(1-P))*MAGIC_COEFF
        print "\texpected: %f magic: %f" %(expected, magic)

        idx=0
        while idx<len(bytes)-n:
                val=0
                for x in xrange(n):
                        val = val << 8
                        val = val | ord(bytes[idx+x])

                histo[val]+=1
                idx+=1

                count=histo[val]
                if count - expected > magic:
                        print "\tfailed: %s occured %d times" %( hex(val), count)
                        return True

        # need this check because the absence of certain bytes is also
        # a sign something is up
        for i in xrange(len(histo)):
                count = histo[i]
                if expected-count > magic:
                        print "\tfailed: %s occured %d times" %( hex(i), count)
                        return True

        print ""

        return False

def main():
        for f in sys.argv[1:]:
                print f
                rand_bytes = get_random_bytes(f)

                if failed_n_gram(3,rand_bytes):
                        continue

                if failed_n_gram(2,rand_bytes):
                        continue

                if failed_n_gram(1,rand_bytes):
                        continue


if __name__ == "__main__":
        main()

我觉得这很合理:

$ entropy.py ~/bin/entropy.py entropy.py.enc entropy.py.zip 
/Users/steve/bin/entropy.py
        1-gram analysis
        N: 1680 states: 256
        expected: 6.000000 magic: 10.226918
        failed: 0xa occured 17 times
entropy.py.enc
        1-gram analysis
        N: 1744 states: 256
        expected: 6.000000 magic: 10.419895

entropy.py.zip
        1-gram analysis
        N: 821 states: 256
        expected: 3.000000 magic: 7.149270
        failed: 0x0 occured 11 times

在这里 .enc 源是否经过:

openssl enc -aes-256-cbc -in entropy.py -out entropy.py.enc

和 .zip 不言自明。

值得注意的几个问题:

1. 它不检查整个文件,只检查文件的第一个kb,然后检查文件中的随机块。因此,如果一个文件是随机数据,附加了一个jpeg,它会愚弄程序。唯一确定是否检查整个文件的方法。

2. 根据我的经验,代码可靠地检测文件何时未加密(因为几乎所有有用的数据都有结构),但由于其统计性质,有时可能会误诊加密/随机文件。

3. 正如已经指出的那样,这种分析对于OTP来说是失败的,因为你可以让它说出你想要的任何东西。

4. 自担风险使用,当然不是检查结果的唯一方法。

其中一种方法是使用一些标准算法(如zip)压缩源数据。如果解密后你可以解压结果-它是正确解密的。压缩通常是在加密之前由加密程序完成的,因为这是BruteForcer在每次尝试时都需要重复的另一个步骤,并且会浪费时间,而且由于加密数据几乎肯定是不可压缩的(使用链式算法压缩后大小不会减小)。

如果没有更明确的场景,我只能指出 cryptanalysis methods . 我想说,验证结果是密码分析的一个简单部分,这是公认的。与解密已知的密码相比,彻底的验证检查只需要很少的CPU。

你真的在问这样的问题吗? 如果知道里面有什么,你就不需要解密了,对吧?

不知何故,这与编程问题无关,它更具数学意义。我在大学上了一些加密数学课。

如果没有大量的数据点,就无法确认。 当然,如果你的结果是有意义的,而且很清楚,它是有意义的,用简单的英语(或任何语言)但回答你的问题。

如果你能够解密,你也应该能够加密。 所以,使用反向解密过程对结果进行加密,如果得到相同的结果,那么您可能是黄金级的……如果不是,可能有什么问题。