EITC/IS/ACC高级古典密码学

在当前时代之前，密码学几乎是加密的同义词，将信息从可读变为难以理解的废话。 为了防止攻击者获得对加密消息的访问权限，发送者只与预期的接收者共享解码过程。 Alice（“A”）代表发送者，Bob（“B”）代表预期接收者，Eve（“窃听者”）代表对手，这些名称在密码学文献中经常使用。

自第一次世界大战中转子密码机的发展和第二次世界大战中计算机的引入以来，密码学方法变得越来越复杂，其应用也更加多样化。

现代密码学高度依赖数学理论和计算机科学实践； 加密方法是围绕计算难度假设建立的，这使得任何对手在实践中都难以破解。 虽然理论上可以闯入一个设计良好的系统，但在实践中这样做是不可能的。 如果构造得当，此类方案被称为“计算安全”； 然而，理论上的突破（例如，整数分解方法的改进）和更快的计算技术需要不断地重新评估，如果需要，还需要对这些设计进行调整。 有一些理论上安全的系统，例如一次性便笺簿，即使具有无限的计算能力，也可以证明是牢不可破的，但在实践中，它们比理论上可破解但计算安全的最佳方案更难应用。

在信息时代，密码技术的进步带来了各种法律挑战。 许多国家将密码学归类为一种武器，由于其潜在的间谍活动和煽动性，限制或禁止其使用和出口。 在密码学合法的一些地方，调查人员可以强制交出与调查相关的文件的加密密钥。 就数字媒体而言，密码学在数字版权管理和版权侵权冲突中也起着关键作用。

XNUMX 世纪，埃德加·爱伦·坡 (Edgar Allan Poe) 的短篇小说《金虫》(The Gold-Bug) 首次使用了“密码学”一词（与“密码图”相对）。

直到最近，密码学几乎只提到“加密”，即将普通数据（称为明文）转换为不可读格式（称为密文）的行为。 解密与加密相反，即从难以理解的密文变为明文。 密码（或密码）是一组以相反顺序执行加密和解密的技术。 算法以及在每种情况下的“密钥”负责密码的详细执行。 密钥是用于解密密文的秘密（最好只有通信者知道）。 它通常是一串字符（最好是短的，以便用户记住它）。 “密码系统”是有限潜在明文、密文、密钥以及与正式数学术语中的每个密钥相对应的加密和解密过程的元素的有序集合。 密钥在形式上和实践上都至关重要，因为仅使用密码信息就可以轻松破解具有固定密钥的密码，从而使它们在大多数情况下无用（甚至适得其反）。

从历史上看，密码经常在没有任何额外程序的情况下使用，例如加密或解密的身份验证或完整性检查。 密码系统分为两类：对称和非对称。 相同的密钥（秘密密钥）用于加密和解密对称系统中的消息，直到 1970 年代，对称系统才为人所知。 因为对称系统使用较短的密钥长度，所以对称系统中的数据操作比非对称系统中的要快。 非对称系统使用“公钥”加密通信，并使用类似的“私钥”对其进行解密。 由于难以确定两个密钥之间的关系，非对称系统的使用提高了通信安全性。 RSA（Rivest-Shamir-Adleman）和 ECC 是非对称系统（椭圆曲线密码术）的两个例子。 取代早期 DES 的广泛使用的 AES（高级加密标准）是高质量对称算法（数据加密标准）的一个例子。 各种儿童语言纠缠技术，例如 Pig Latin 或其他 cant，以及实际上所有密码方案，无论多么严肃，在 XNUMX 世纪初引入一次性便笺簿之前的任何来源，都是低质量的例子对称算法。

术语“代码”通常通俗地用于指代任何加密或消息隐藏技术。 然而，在密码学中，代码是指用一个代码字替换一个明文单元（即，一个有意义的词或短语）（例如，“wallaby”替换“attack at early”）。 相反，密文是通过修改或替换低于该级别的元素（例如，字母、音节或一对字母）以形成密文而创建的。

密码分析是研究在无需访问所需密钥的情况下解密加密数据的方法； 换句话说，它是研究如何“破解”加密方案或其实现。

在英语中，有些人可以互换使用术语“密码学”和“密码学”，而其他人（包括一般的美国军事实践）使用“密码学”来指代密码技术的使用和实践，而“密码学”指的是组合研究密码学和密码分析。 英语比许多其他语言更具适应性，其中“密码学”（由密码学家实践）总是在第二种意义上使用。 根据 RFC 2828，隐写术有时包含在密码学中。

密码语言学是对与密码学或密码学相关的语言属性的研究（例如，频率统计、字母组合、通用模式等）。

密码学和密码分析有着悠久的历史。
密码学史是主要文章。
在现代之前，密码学主要关注消息的机密性（即加密）——将消息从可理解的形式转换为不可理解的形式，并再次使没有秘密知识（即解密所需的密钥）的拦截器或窃听者无法读取它们该消息的）。 加密旨在使间谍、军事领导人和外交官的谈话保密。 近几十年来，该学科已经发展到结合诸如消息完整性检查、发送者/接收者身份认证、数字签名、交互式证明和安全计算等技术。

两种最常见的经典密码类型是转置密码，它系统地将字母或字母组替换为其他字母或字母组（例如，“hello world”在简单的重新排列方案中变为“ehlol owrdl”），以及替换密码，它系统地用其他字母或字母组替换字母或字母组（例如，“立即飞行”变为“gmz bu”的简单版本从未为狡猾的对手提供太多隐私。凯撒密码是一种早期的替换密码，其中明文中的每个字母都被替换为字母表中一定数量的字母。根据 Suetonius 的说法，Julius Caesar 使用它与三人轮班来与他的将军们交流。早期的希伯来密码 Atbash 就是一个例子。已知最古老的密码学用法是在埃及（约公元前 1900 年）刻在石头上的密文，但这样做可能是为了让有文化的观众欣赏，而不是a 隐藏信息。

据报道，古希腊人已经知道地穴（例如，声称已被斯巴达军队使用的 scytale 换位密码）。 隐写术（甚至隐藏通信的存在以保持其私密性的做法）也在古代发明。 根据希罗多德的说法，一个短语纹身在奴隶剃光的头上，隐藏在重新长出的头发下。 使用隐形墨水、微点和数字水印来隐藏信息是隐写术的最新实例。

Kautiliyam 和 Mulavediya 是印度 2000 年历史的 Vtsyyana 的 Kamasutra 中提到的两种密码。 Kautiliyam 中的密码字母替换基于语音关系，例如元音变为辅音。 Mulavediya 中的密码字母表由匹配字母和倒数字母组成。

根据穆斯林学者伊本·纳迪姆（Ibn al-Nadim）的说法，萨珊王朝的波斯有两种秘密文字：用于官方通信的 h-dabrya（字面意思是“国王的文字”）和用于与其他国家交换秘密信息的 rz-saharya国家。

大卫·卡恩在他的《密码破译者》一书中写道，当代密码学始于阿拉伯人，他们是第一个仔细记录密码分析程序的人。 加密信息书由 Al-Khalil (717–786) 撰写，其中包含最早使用排列和组合来列出所有可以想象的带元音和不带元音的阿拉伯语单词。

由经典密码（以及一些现代密码）生成的密文揭示了有关明文的统计信息，可用于破解密码。 在发现频率分析后，几乎所有此类密码都可能被智能攻击者破解，可能是 9 世纪的阿拉伯数学家和博学家 Al-Kindi（也称为 Alkindus）。 古典密码今天仍然很流行，尽管主要是作为谜题（见密码）。 Risalah fi Istikhraj al-Mu'amma（解密密码消息手稿）由 Al-Kindi 编写，记录了频率分析密码分析技术的第一个已知用途。

一些扩展历史加密方法，例如谐音密码，倾向于使频率分布变平，可能不会从语言字母频率中受益。 语言字母组（或 n-gram）频率可能会对这些密码造成攻击。

在发现多字母密码之前，最著名的是 Leon Battista Alberti 大约在 1467 年左右，几乎所有密码都可以使用频率分析方法进行密码分析，尽管有一些证据表明 Al-Kindi 已经知道它。 Alberti 提出了对通信的不同部分使用单独的密码（或替代字母）的想法（也许对于每个连续的明文字母都在限制范围内）。 他还创造了被认为是第一个自动加密设备，一个执行他设计的一部分的轮子。 Vigenère 密码（一种多字母密码）中的加密由一个关键字控制，该关键字根据使用关键字的哪个字母来控制字母替换。 Charles Babbage 在 XNUMX 世纪中叶证明了 Vigenère 密码容易受到 Kasiski 分析的影响，但 Friedrich Kasiski 十年后发表了他的发现。

尽管频率分析是针对许多密码的强大而广泛的技术，但加密在实践中仍然有效，因为许多潜在的密码分析家不知道该技术。 在不使用频率分析的情况下破解消息需要了解所使用的密码以及可能涉及的密钥，这使得间谍、贿赂、入室盗窃、叛逃和其他密码分析不知情的策略更具吸引力。 密码算法的秘密最终在 19 世纪被承认为既不合理也不可行的消息安全保证。 事实上，任何适当的密码方案（包括密码）都应该保持安全，即使对手完全理解密码算法本身。 密钥的安全性应该足以让一个好的密码在面对攻击时保持机密性。 Auguste Kerckhoffs 于 1883 年首次提出这一基本原理，称为 Kerckhoffs 原理； 或者，更直言不讳的是，信息论和理论密码学基础的发明者克劳德·香农将其重申为香农的格言——“敌人知道系统”。

为了帮助密码，已经使用了许多物理小工具和帮助。 古希腊的 scytale 是一种据称被斯巴达人用作转置密码工具的棒，可能是最早的一种。 其他辅助工具是在中世纪设计的，例如密码格栅，它也用于隐写术。 随着多字母密码的发展，更复杂的辅助工具如 Alberti 的密码盘、Johannes Trithemius 的 tabula recta 方案和 Thomas Jefferson 的轮式密码变得可用（不为公众所知，并在 1900 年左右由 Bazeries 独立重新发明）。 许多机械加密/解密系统是在 1920 世纪初设计并获得专利的，其中包括从 XNUMX 年代后期到二战期间德国政府和军队广泛使用的转子机器。 第一次世界大战之后，由这些机器设计的更高质量实例实施的密码导致密码分析难度显着增加。

密码学主要关注 XNUMX 世纪初之前的语言和字典模式。 从那时起，重点已经发展，密码学现在包括信息论、计算复杂性、统计学、组合学、抽象代数、数论和一般有限数学的各个方面。 密码学是一种工程，但它的独特之处在于它处理主动、智能和敌对的抵抗，而其他类型的工程（如土木或化学工程）只需要处理中性的自然力。 密码学困难与量子物理学之间的联系也在研究中。

数字计算机和电子设备的发展通过允许创建相当复杂的密码来辅助密码分析。 此外，与专门加密书面语言文本的传统密码不同，计算机允许加密可以以任何二进制格式表示的任何类型的数据。 这是新颖而重要的。 在密码设计和密码分析中，计算机已经取代了语言密码学。 与主要直接操作传统字符（即字母和数字）的经典和机械方法不同，许多计算机密码对二进制位序列（偶尔以组或块）进行操作。 另一方面，计算机辅助密码分析，这部分补偿了密码复杂性的增加。 尽管如此，好的现代密码仍然领先于密码分析。 通常情况下，使用一个好的密码是非常有效的（即快速且需要很少的资源，例如内存或 CPU 能力），而破解它需要的工作量要大很多数量级，而且远远大于任何经典密码，有效地使密码分析变得不可能。

现代密码学首次亮相。
事实证明，新机械设备的密码分析具有挑战性且耗时。 二战期间，英国布莱切利公园的密码分析活动促进了发明更有效的重复性任务方法。 Colossus 是世界上第一台完全电子化、数字化、可编程的计算机，旨在帮助对德国陆军 Lorenz SZ40/42 机器创建的密码进行解码。

密码学是一个相对较新的开放学术研究领域，始于 1970 年代中期。 IBM 员工设计了成为联邦（即美国）数据加密标准的算法； Whitfield Diffie 和 Martin Hellman 发表了他们的密钥协商算法； 和 Martin Gardner 的《科学美国人》专栏发表了 RSA 算法。 从那时起，密码学作为一种通信、计算机网络和计算机安全技术而广受欢迎。

与抽象数学有着深刻的联系，因为一些现代密码学方法只能在某些数学问题难以解决的情况下保密其密钥，例如整数分解或离散对数问题。 只有少数密码系统被证明是 100% 安全的。 Claude Shannon 证明了一次性便笺簿就是其中之一。 有一些关键算法已被证明在某些条件下是安全的。 例如，无法分解非常大的整数是相信 RSA 和其他系统是安全的基础，但无法证明不可破坏性，因为潜在的数学问题仍未解决。 在实践中，这些被广泛使用，大多数有能力的观察者认为它们在实践中是牢不可破的。 存在类似于 RSA 的系统，例如由 Michael O. Rabin 开发的系统，如果分解 n = pq 是不可能的，则可以证明是安全的； 但是，它们实际上毫无用处。 离散对数问题是相信其他一些密码系统是安全的基础，并且有类似的、不太实用的系统在离散对数问题的可解性或不可解性方面可证明是安全的。

密码算法和系统设计人员在研究他们的想法时必须考虑未来可能的进展，此外还要了解密码历史。 例如，随着计算机处理能力的提高，蛮力攻击的广度也在增加，因此所需的密钥长度也在增加。 一些探索后量子密码学的密码系统设计者已经在考虑量子计算的潜在后果。 这些机器的适度实施的宣布迫在眉睫，这可能使得需要先发制人的谨慎而不仅仅是投机。

现代古典密码学

对称（或私钥）密码术是一种加密类型，其中发送者和接收者使用相同的密钥（或者，不太常见的是，它们的密钥不同，但以易于计算的方式相关并且保密，私下保存） ）。 直到 1976 年 XNUMX 月，这是唯一为公众所知的加密类型。

分组密码和流密码都用于实现对称密钥密码。 块密码以明文块而不是单个字符的形式加密输入，就像流密码一样。

美国政府已将数据加密标准 (DES) 和高级加密标准 (AES) 指定为加密标准（尽管 AES 建立后 DES 的认证最终被撤销）。 DES（尤其是其仍被批准且安全得多的三重 DES 变体）尽管已被弃用为官方标准，但仍然很受欢迎； 它用于广泛的应用，从 ATM 加密到电子邮件隐私和安全远程访问。 已经发明和发布了许多不同的分组密码，并取得了不同程度的成功。 许多，包括一些由合格的从业者设计的，如 FEAL，已被广泛破坏。

与分组密码不同，流密码生成无限长的密钥材料流，该流与明文逐位或逐字符耦合，类似于一次性密码。 流密码的输出流是从隐藏的内部状态生成的，该状态会随着密码的功能而变化。 密钥材料首先用于设置该内部状态。 流密码RC4被广泛使用。 通过创建密钥流的块（而不是伪随机数生成器）并使用密钥流的每一位对明文的每一位进行异或运算，可以将块密码用作流密码。

消息验证码 (MAC) 类似于加密散列函数，不同之处在于可以使用密钥在收到时验证散列值； 这种额外的复杂性可以防止对裸摘要算法的攻击，因此被认为是值得的。 第三种加密技术是加密散列函数。 例如，它们将任何长度的消息作为输入，并输出一个小的、固定长度的散列，可用于数字签名。 攻击者无法使用良好的散列算法找到两条产生相同散列的消息。 MD4 是一种广泛使用但现在有缺陷的哈希函数； MD5 是 MD4 的增强形式，同样被广泛使用，但在实践中被打破。 Secure Hash Algorithm 系列类似 MD5 的哈希算法由美国国家安全局开发：美国标准权威机构认为，从安全的角度来看，制定一个“显着提高 NIST 整体哈希算法的鲁棒性”的新标准是“谨慎的”工具包。” SHA-1 被广泛使用并且比 MD5 更安全，但是密码分析家已经识别出针对它的攻击； SHA-2 系列对 SHA-1 进行了改进，但自 2011 年起就容易受到冲突的影响； SHA-2 家族在 SHA-1 的基础上进行了改进，但容易发生冲突因此，到 2012 年，将举行哈希函数设计竞赛，以挑选新的美国国家标准，即 SHA-3。 比赛于 2 年 2012 月 3 日结束，当时美国国家标准与技术研究院 (NIST) 宣布 Keccak 作为新的 SHA-XNUMX 哈希算法。 与可逆块密码和流密码不同，密码散列函数提供了不能用于​​恢复原始输入数据的散列输出。 加密哈希函数用于检查从不可靠来源获取的数据的真实性或增加额外的保护程度。

尽管一条消息或一组消息可以具有与其他消息不同的密钥，但对称密钥密码系统使用相同的密钥进行加密和解密。 安全使用对称密码所需的密钥管理是一个很大的缺点。 理想情况下，每一对通信方应该共享一个不同的密钥，并且可能为每个发送的密文共享一个不同的密文。 所需密钥的数量与网络参与者的数量成正比增长，因此需要复杂的密钥管理技术来保持它们的一致性和保密性。

Whitfield Diffie 和 Martin Hellman 在 1976 年的一项开创性工作中发明了公钥（也称为非对称密钥）密码学的概念，其中使用了两个不同但在数学上相关的密钥——公钥和私钥。 尽管它们是密不可分的，但公钥系统的构建方式使得从另一个（“公钥”）计算一个密钥（“私钥”）在计算上是不可行的。 相反，两个密钥都是秘密生成的，作为一个链接对。 根据历史学家大卫卡恩的说法，公钥密码学是“自文艺复兴时期出现多字母替代以来，该领域最具革命性的新概念”。

公钥密码系统中的公钥可以自由传输，但耦合的私钥必须隐藏。 公钥用于加密，而私钥或秘密密钥用于公钥加密方案中的解密。 虽然 Diffie 和 Hellman 无法创建这样的系统，但他们通过提供 Diffie-Hellman 密钥交换协议证明了公钥密码学是可以想象的，该解决方案允许两个人秘密地就共享加密密钥达成一致。 最广泛使用的公钥证书格式由 X.509 标准定义。

Diffie 和 Hellman 的出版引发了学术界对开发实用的公钥加密系统的广泛兴趣。 Ronald Rivest、Adi Shamir 和 Len Adleman 最终在 1978 年赢得了比赛，他们的答案被称为 RSA 算法。

除了是最早公开的高质量公钥算法实例之外，Diffie-Hellman 和 RSA 算法也是最常用的算法之一。 Cramer-Shoup 密码系统、ElGamal 加密和众多椭圆曲线方法都是非对称密钥算法的示例。

根据英国情报组织政府通信总部 (GCHQ) 于 1997 年发布的一份文件，GCHQ 密码学家预见到了几项学术进步。 据传说，非对称密钥密码术是由 James H. Ellis 于 1970 年左右发明的。Clifford Cocks 于 1973 年发明了一种在设计上与 RSA 极为相似的解决方案。 Malcolm J. Williamson 在 1974 年发明了 Diffie-Hellman 密钥交换。

数字签名系统也使用公钥密码术来实现。 数字签名与传统签名相似，用户创建简单但他人难以伪造。 数字签名也可以永久链接到正在签名的通信内容； 这意味着它们不能在不被发现的情况下从一个文档“移动”到另一个文档。 数字签名方案中有两种算法：一种用于签名，它使用密钥来处理消息（或消息的哈希，或两者兼而有之），另一种用于验证，它使用与消息匹配的公钥来验证签名的真实性。 最常用的两种数字签名方法是 RSA 和 DSA。 公钥基础设施和许多网络安全系统（例如 SSL/TLS、许多 VPN）依赖数字签名来运行。

“难”问题的计算复杂性，例如数论中的问题，经常用于开发公钥方法。 整数分解问题与 RSA 的难度有关，而离散对数问题与 Diffie-Hellman 和 DSA 有关。 椭圆曲线密码学的安全性是基于椭圆曲线数论问题。 大多数公钥算法包括模乘和求幂等运算，由于潜在问题的难度，它们的计算成本比大多数分组密码中使用的技术要高得多，尤其是在正常密钥大小的情况下。 因此，公钥密码系统通常是混合密码系统，其中消息使用快速、高质量的对称密钥算法加密，而相关的对称密钥与消息一起发送但使用公钥算法加密。 混合签名方案也常用，其中计算加密散列函数并且仅对生成的散列进行数字签名。

密码学中的哈希函数

加密哈希函数是一种加密算法，它产生和使用特定密钥来加密数据以进行对称或非对称加密，它们可以被认为是密钥。 例如，它们将任何长度的消息作为输入，并输出一个小的、固定长度的散列，可用于数字签名。 攻击者无法使用良好的散列算法找到两条产生相同散列的消息。 MD4 是一种广泛使用但现在有缺陷的哈希函数； MD5 是 MD4 的增强形式，同样被广泛使用，但在实践中被打破。 Secure Hash Algorithm 系列类似 MD5 的哈希算法由美国国家安全局开发：美国标准权威机构认为，从安全的角度来看，制定一个“显着提高 NIST 整体哈希算法的鲁棒性”的新标准是“谨慎的”工具包。” SHA-1 被广泛使用并且比 MD5 更安全，但是密码分析家已经识别出针对它的攻击； SHA-2 系列对 SHA-1 进行了改进，但自 2011 年起就容易受到冲突的影响； SHA-2 家族在 SHA-1 的基础上进行了改进，但容易发生冲突因此，到 2012 年，将举行哈希函数设计竞赛，以挑选新的美国国家标准，即 SHA-3。 比赛于 2 年 2012 月 3 日结束，当时美国国家标准与技术研究院 (NIST) 宣布 Keccak 作为新的 SHA-XNUMX 哈希算法。 与可逆块密码和流密码不同，密码散列函数提供了不能用于​​恢复原始输入数据的散列输出。 加密哈希函数用于检查从不可靠来源获取的数据的真实性或增加额外的保护程度。

密码原语和密码系统

密码学的大部分理论工作都集中在密码原语——具有基本密码属性的算法——以及它们如何与其他密码挑战相关联。 然后使用这些基本原语来创建更复杂的加密工具。 这些原语提供了用于创建更复杂的工具的基本品质，这些工具称为密码系统或密码协议，可确保一个或多个高级安全属性。 另一方面，密码原语和密码系统之间的界限是任意的。 例如，RSA 算法有时被视为密码系统，有时被视为原语。 伪随机函数、单向函数和其他密码原语是常见的例子。

密码系统或密码系统是通过组合一个或多个密码原语来创建更复杂的算法而创建的。 密码系统（例如，El-Gamal 加密）旨在提供特定功能（例如，公钥加密），同时确保某些安全质量（例如，随机预言模型选择明文攻击 CPA 安全）。 为了支持系统的安全质量，密码系统利用底层密码原语的属性。 一个复杂的密码系统可以从许多更基本的密码系统的组合中生成，因为原语和密码系统之间的区别有些武断。 在许多情况下，密码系统的结构包括两方或多方在空间中（例如，在安全消息的发送者和接收者之间）或跨时间（例如，在安全消息的发送者和接收者之间）的来回通信（例如，加密保护的备份数据）。