学号:16030140019
姓名: 莫益彰
【嵌牛导读】:凯撒密码是一种简单的加密方法,即将文本中的每一个字符都位移相同的位置。如选定位移3位:
原文:a b c
密文:d e f
由于出现了字母频度分析,凯撒密码变得很容易破解,因此人们在单一恺撒密码的基础上扩展出多表密码,称为“维吉尼亚”密码。
【嵌牛鼻子】密码学,计算机安全。
【嵌牛提问】维吉尼亚怎么破解,8位维吉尼亚是否可破?维吉尼亚算法的时间复杂度?
【嵌牛正文】
维吉尼亚密码的加密
维吉尼亚密码由凯撒密码扩展而来,引入了密钥的概念。即根据密钥来决定用哪一行的密表来进行替换,以此来对抗字频统计。假如以上面第一行代表明文字母,左面第一列代表密钥字母,对如下明文加密:
TO BE OR NOT TO BE THAT IS THE QUESTION
当选定RELATIONS作为密钥时,加密过程是:明文一个字母为T,第一个密钥字母为R,因此可以找到在R行中代替T的为K,依此类推,得出对应关系如下:
密钥:RE LA TI ONS RE LA TION SR ELA TIONSREL
明文:TO BE OR NOT TO BE THAT IS THE QUESTION
密文:KS ME HZ BBL KS ME MPOG AJ XSE JCSFLZSY
图解加密过程:
在维吉尼亚(Vigenère)的密码中,发件人和收件人必须使用同一个关键词(或者同一文字章节),这个关键词或文字章节中的字母告诉他们怎么样才能前后改变字母的位置来获得该段信息中的每个字母的正确对应位置。
维吉尼亚密码的破解
维吉尼亚密码分解后实则就是多个凯撒密码,只要知道密钥的长度,我们就可以将其分解。
如密文为:ABCDEFGHIJKLMN
如果我们知道密钥长度为3,就可将其分解为三组:
组1:A D G J N
组2:B E H K
组3:C F I M
分解后每组就是一个凯撒密码,即组内的位移量是一致的,对每一组即可用频度分析法来解密。
所以破解维吉尼亚密码的关键就是确定密钥的长度。
确定密钥长度
确定密钥长度主要有两种方法,Kasiski 测试法相对简单很多,但Friedman 测试法的效果明显优于Kasiski 测试法。
Kasiski 测试法
在英文中,一些常见的单词如the有几率被密钥的相同部分加密,即原文中的the可能在密文中呈现为相同的三个字母。
在这种情况下,相同片段的间距就是密文长度的倍数。
所以我们可以通过在密文中找到相同的片段,计算出这些相同片段之间的间距,而密钥长度理论上就是这些间距的公约数。
然后我们需要知道重合指数(IC, index of coincidence)的概念。
重合指数表示两个随机选出的字母是相同的的概率,即随机选出两个A的概率+随机选出两个B的概率+随机选出两个C的概率+……+随机选出两个Z的概率。
对英语而言,根据上述的频率表,我们可以计算出英语文本的重合指数为
P(A)^2 + P(B)^2+……+P(Z)^2 = 0.65
利用重合指数推测密钥长度的原理在于,对于一个由凯撒密码加密的序列,由于所有字母的位移程度相同,所以密文的重合指数应等于原文语言的重合指数。
据此,我们可以逐一计算不同密钥长度下的重合指数,当重合指数接近期望的0.65时,我们就可以推测这是我们所要找的密钥长度。
举例来说,对密文ABCDEABCDEABCDEABC
首先测试密钥长度=1,对密文ABCDEABCDEABCDEABC统计每个字符出现的次数:
A: 4 B: 4 C: 4 D:3 E:3
那么对于该序列的重合指数就为:(4/18)^2 + (4/18)^2 + (4/18)^2 +(3/18)^2 +(3/18)^2 != 0.65
然后测试密钥长度=2,将密文ABCDEABCDEABCDEABC分解为两组:
组1:A C E B D A C E B
组2:B D A C E B D A C
我们知道如果密钥长度真的是2,那么组1,组2都是一个凯撒密码。对组1组2分别计算重合指数。
如果组1的重合指数接近0.65,组2的重合指数也接近0.65,那么基本可以断定密钥长度为2。
在知道了密钥长度n以后,就可将密文分解为n组,每一组都是一个凯撒密码,然后对每一组用字母频度分析进行解密,和在一起就能成功解密凯撒密码。
上文已经说到,自然语言的字母频度是一定的。字母频度分析就是将密文的字母频度和自然语言的自然频度排序对比,从而找出可能的原文。
密码学是研究编制密码和破译密码的技术科学。研究密码变化的客观规律,应用于编制密码以保守通信秘密的,称为编码学;应用于破译密码以获取通信情报的,称为破译学,总称密码学。
密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照这些法则,变明文为密文,称为加密变换;变密文为明文,称为脱密变换。密码在早期仅对文字或数码进行加、脱密变换,随着通信技术的发展,对语音、图像、数据等都可实施加、脱密变换。
密码学是在编码与破译的斗争实践中逐步发展起来的,并随着先进科学技术的应用,已成为一门综合性的尖端技术科学。它与语言学、数学、电子学、声学、信息论、计算机科学等有着广泛而密切的联系。它的现实研究成果,特别是各国政府现用的密码编制及破译手段都具有高度的机密性。
进行明密变换的法则,称为密码的体制。指示这种变换的参数,称为密钥。它们是密码编制的重要组成部分。密码体制的基本类型可以分为四种:错乱——按照规定的图形和线路,改变明文字母或数码等的位置成为密文;代替——用一个或多个代替表将明文字母或数码等代替为密文;密本——用预先编定的字母或数字密码组,代替一定的词组单词等变明文为密文;加乱——用有限元素组成的一串序列作为乱数,按规定的算法,同明文序列相结合变成密文。以上四种密码体制,既可单独使用,也可混合使用 ,以编制出各种复杂度很高的实用密码。
20世纪70年代以来,一些学者提出了公开密钥体制,即运用单向函数的数学原理,以实现加、脱密密钥的分离。加密密钥是公开的,脱密密钥是保密的。这种新的密码体制,引起了密码学界的广泛注意和探讨。
利用文字和密码的规律,在一定条件下,采取各种技术手段,通过对截取密文的分析,以求得明文,还原密码编制,即破译密码。破译不同强度的密码,对条件的要求也不相同,甚至很不相同。
中国古代秘密通信的手段,已有一些近于密码的雏形。宋曾公亮、丁度等编撰《武经总要》“字验”记载,北宋前期,在作战中曾用一首五言律诗的40个汉字,分别代表40种情况或要求,这种方式已具有了密本体制的特点。
1871年,由上海大北水线电报公司选用6899个汉字,代以四码数字,成为中国最初的商用明码本,同时也设计了由明码本改编为密本及进行加乱的方法。在此基础上,逐步发展为各种比较复杂的密码。
在欧洲,公元前405年,斯巴达的将领来山得使用了原始的错乱密码;公元前一世纪,古罗马皇帝凯撒曾使用有序的单表代替密码;之后逐步发展为密本、多表代替及加乱等各种密码体制。
二十世纪初,产生了最初的可以实用的机械式和电动式密码机,同时出现了商业密码机公司和市场。60年代后,电子密码机得到较快的发展和广泛的应用,使密码的发展进入了一个新的阶段。
密码破译是随着密码的使用而逐步产生和发展的。1412年,波斯人卡勒卡尚迪所编的百科全书中载有破译简单代替密码的方法。到16世纪末期,欧洲一些国家设有专职的破译人员,以破译截获的密信。密码破译技术有了相当的发展。1863年普鲁士人卡西斯基所著《密码和破译技术》,以及1883年法国人克尔克霍夫所著《军事密码学》等著作,都对密码学的理论和方法做过一些论述和探讨。1949年美国人香农发表了《秘密体制的通信理论》一文,应用信息论的原理分析了密码学中的一些基本问题。
自19世纪以来,由于电报特别是无线电报的广泛使用,为密码通信和第三者的截收都提供了极为有利的条件。通信保密和侦收破译形成了一条斗争十分激烈的隐蔽战线。
1917年,英国破译了德国外长齐默尔曼的电报,促成了美国对德宣战。1942年,美国从破译日本海军密报中,获悉日军对中途岛地区的作战意图和兵力部署,从而能以劣势兵力击破日本海军的主力,扭转了太平洋地区的战局。在保卫英伦三岛和其他许多著名的历史事件中,密码破译的成功都起到了极其重要的作用,这些事例也从反面说明了密码保密的重要地位和意义。
当今世界各主要国家的政府都十分重视密码工作,有的设立庞大机构,拨出巨额经费,集中数以万计的专家和科技人员,投入大量高速的电子计算机和其他先进设备进行工作。与此同时,各民间企业和学术界也对密码日益重视,不少数学家、计算机学家和其他有关学科的专家也投身于密码学的研究行列,更加速了密码学的发展。
现在密码已经成为单独的学科,从传统意义上来说,密码学是研究如何把信息转换成一种隐蔽的方式并阻止其他人得到它。
密码学是一门跨学科科目,从很多领域衍生而来:它可以被看做是信息理论,却使用了大量的数学领域的工具,众所周知的如数论和有限数学。
原始的信息,也就是需要被密码保护的信息,被称为明文。加密是把原始信息转换成不可读形式,也就是密码的过程。解密是加密的逆过程,从加密过的信息中得到原始信息。cipher是加密和解密时使用的算法。
最早的隐写术只需纸笔,现在称为经典密码学。其两大类别为置换加密法,将字母的顺序重新排列;替换加密法,将一组字母换成其他字母或符号。经典加密法的资讯易受统计的攻破,资料越多,破解就更容易,使用分析频率就是好办法。经典密码学现在仍未消失,经常出现在智力游戏之中。在二十世纪早期,包括转轮机在内的一些机械设备被发明出来用于加密,其中最著名的是用于第二次世界大战的密码机Enigma。这些机器产生的密码相当大地增加了密码分析的难度。比如针对Enigma各种各样的攻击,在付出了相当大的努力后才得以成功。
传统密码学
Autokey密码
置换密码
二字母组代替密码 (by Charles Wheatstone)
多字母替换密码
希尔密码
维吉尼亚密码
替换密码
凯撒密码
ROT13
仿射密码
Atbash密码
换位密码
Scytale
Grille密码
VIC密码 (一种复杂的手工密码,在五十年代早期被至少一名苏联间谍使用过,在当时是十分安全的)
对传统密码学的攻击
频率分析
重合指数
现代算法,方法评估与选择工程
标准机构
the Federal Information Processing Standards Publication program (run by NIST to produce standards in many areas to guide operations of the US Federal government; many FIPS Pubs are cryptography related, ongoing)
the ANSI standardization process (produces many standards in many areas; some are cryptography related, ongoing)
ISO standardization process (produces many standards in many areas; some are cryptography related, ongoing)
IEEE standardization process (produces many standards in many areas; some are cryptography related, ongoing)
IETF standardization process (produces many standards (called RFCs) in many areas; some are cryptography related, ongoing)
See Cryptography standards
加密组织
NSA internal evaluation/selections (surely extensive, nothing is publicly known of the process or its results for internal use; NSA is charged with assisting NIST in its cryptographic responsibilities)
GCHQ internal evaluation/selections (surely extensive, nothing is publicly known of the process or its results for GCHQ use; a division of GCHQ is charged with developing and recommending cryptographic standards for the UK government)
DSD Australian SIGINT agency - part of ECHELON
Communications Security Establishment (CSE) — Canadian intelligence agency.
公开的努力成果
the DES selection (NBS selection process, ended 1976)
the RIPE division of the RACE project (sponsored by the European Union, ended mid-'80s)
the AES competition (a 'break-off' sponsored by NIST; ended 2001)
the NESSIE Project (evaluation/selection program sponsored by the European Union; ended 2002)
the CRYPTREC program (Japanese government sponsored evaluation/recommendation project; draft recommendations published 2003)
the Internet Engineering Task Force (technical body responsible for Internet standards -- the Request for Comment series: ongoing)
the CrypTool project (eLearning programme in English and German; freeware; exhaustive educational tool about cryptography and cryptanalysis)
加密散列函数 (消息摘要算法,MD算法)
加密散列函数
消息认证码
Keyed-hash message authentication code
EMAC (NESSIE selection MAC)
HMAC (NESSIE selection MAC; ISO/IEC 9797-1, FIPS and IETF RFC)
TTMAC 也称 Two-Track-MAC (NESSIE selection MAC; K.U.Leuven (Belgium) debis AG (Germany))
UMAC (NESSIE selection MAC; Intel, UNevada Reno, IBM, Technion, UCal Davis)
MD5 (系列消息摘要算法之一,由MIT的Ron Rivest教授提出; 128位摘要)
SHA-1 (NSA开发的160位摘要,FIPS标准之一;第一个发行发行版本被发现有缺陷而被该版本代替; NIST/NSA 已经发布了几个具有更长'摘要'长度的变种; CRYPTREC推荐 (limited))
SHA-256 (NESSIE 系列消息摘要算法, FIPS标准之一180-2,摘要长度256位 CRYPTREC recommendation)
SHA-384 (NESSIE 列消息摘要算法, FIPS标准之一180-2,摘要长度384位; CRYPTREC recommendation)
SHA-512 (NESSIE 列消息摘要算法, FIPS标准之一180-2,摘要长度512位; CRYPTREC recommendation)
RIPEMD-160 (在欧洲为 RIPE 项目开发, 160位摘要;CRYPTREC 推荐 (limited))
Tiger (by Ross Anderson et al)
Snefru
Whirlpool (NESSIE selection hash function, Scopus Tecnologia S.A. (Brazil) K.U.Leuven (Belgium))
公/私钥加密算法(也称 非对称性密钥算法)
ACE-KEM (NESSIE selection asymmetric encryption scheme; IBM Zurich Research)
ACE Encrypt
Chor-Rivest
Diffie-Hellman (key agreement; CRYPTREC 推荐)
El Gamal (离散对数)
ECC(椭圆曲线密码算法) (离散对数变种)
PSEC-KEM (NESSIE selection asymmetric encryption scheme; NTT (Japan); CRYPTREC recommendation only in DEM construction w/SEC1 parameters) )
ECIES (Elliptic Curve Integrated Encryption System; Certicom Corp)
ECIES-KEM
ECDH (椭圆曲线Diffie-Hellman 密钥协议; CRYPTREC推荐)
EPOC
Merkle-Hellman (knapsack scheme)
McEliece
NTRUEncrypt
RSA (因数分解)
RSA-KEM (NESSIE selection asymmetric encryption scheme; ISO/IEC 18033-2 draft)
RSA-OAEP (CRYPTREC 推荐)
Rabin cryptosystem (因数分解)
Rabin-SAEP
HIME(R)
XTR
公/私钥签名算法
DSA(zh:数字签名;zh-tw:数位签章算法) (来自NSA,zh:数字签名;zh-tw:数位签章标准(DSS)的一部分; CRYPTREC 推荐)
Elliptic Curve DSA (NESSIE selection digital signature scheme; Certicom Corp); CRYPTREC recommendation as ANSI X9.62, SEC1)
Schnorr signatures
RSA签名
RSA-PSS (NESSIE selection digital signature scheme; RSA Laboratories); CRYPTREC recommendation)
RSASSA-PKCS1 v1.5 (CRYPTREC recommendation)
Nyberg-Rueppel signatures
MQV protocol
Gennaro-Halevi-Rabin signature scheme
Cramer-Shoup signature scheme
One-time signatures
Lamport signature scheme
Bos-Chaum signature scheme
Undeniable signatures
Chaum-van Antwerpen signature scheme
Fail-stop signatures
Ong-Schnorr-Shamir signature scheme
Birational permutation scheme
ESIGN
ESIGN-D
ESIGN-R
Direct anonymous attestation
NTRUSign用于移动设备的公钥加密算法, 密钥比较短小但也能达到高密钥ECC的加密效果
SFLASH (NESSIE selection digital signature scheme (esp for smartcard applications and similar); Schlumberger (France))
Quartz
密码鉴定
Key authentication
Public key infrastructure
X.509
Public key certificate
Certificate authority
Certificate revocation list
ID-based cryptography
Certificate-based encryption
Secure key issuing cryptography
Certificateless cryptography
匿名认证系统
GPS (NESSIE selection anonymous identification scheme; Ecole Normale Supérieure, France Télécom, La Poste)
秘密钥算法 (也称 对称性密钥算法)
流密码
A5/1, A5/2 (GSM移动电话标准中指定的密码标准)
BMGL
Chameleon
FISH (by Siemens AG)
二战'Fish'密码
Geheimfernschreiber (二战时期Siemens AG的机械式一次一密密码, 被布莱奇利(Bletchley)庄园称为STURGEON)
Schlusselzusatz (二战时期 Lorenz的机械式一次一密密码, 被布莱奇利(Bletchley)庄园称为[[tunny)
HELIX
ISAAC (作为伪随机数发生器使用)
Leviathan (cipher)
LILI-128
MUG1 (CRYPTREC 推荐使用)
MULTI-S01 (CRYPTREC 推荐使用)
一次一密 (Vernam and Mauborgne, patented mid-'20s; an extreme stream cypher)
Panama
Pike (improvement on FISH by Ross Anderson)
RC4 (ARCFOUR) (one of a series by Prof Ron Rivest of MIT; CRYPTREC 推荐使用 (limited to 128-bit key))
CipherSaber (RC4 variant with 10 byte random IV, 易于实现)
SEAL
SNOW
SOBER
SOBER-t16
SOBER-t32
WAKE
分组密码
分组密码操作模式
乘积密码
Feistel cipher (由Horst Feistel提出的分组密码设计模式)
Advanced Encryption Standard (分组长度为128位; NIST selection for the AES, FIPS 197, 2001 -- by Joan Daemen and Vincent Rijmen; NESSIE selection; CRYPTREC 推荐使用)
Anubis (128-bit block)
BEAR (由流密码和Hash函数构造的分组密码, by Ross Anderson)
Blowfish (分组长度为128位; by Bruce Schneier, et al)
Camellia (分组长度为128位; NESSIE selection (NTT Mitsubishi Electric); CRYPTREC 推荐使用)
CAST-128 (CAST5) (64 bit block; one of a series of algorithms by Carlisle Adams and Stafford Tavares, who are insistent (indeed, adamant) that the name is not due to their initials)
CAST-256 (CAST6) (128位分组长度; CAST-128的后继者,AES的竞争者之一)
CIPHERUNICORN-A (分组长度为128位; CRYPTREC 推荐使用)
CIPHERUNICORN-E (64 bit block; CRYPTREC 推荐使用 (limited))
CMEA — 在美国移动电话中使用的密码,被发现有弱点.
CS-Cipher (64位分组长度)
DESzh:数字;zh-tw:数位加密标准(64位分组长度; FIPS 46-3, 1976)
DEAL — 由DES演变来的一种AES候选算法
DES-X 一种DES变种,增加了密钥长度.
FEAL
GDES —一个DES派生,被设计用来提高加密速度.
Grand Cru (128位分组长度)
Hierocrypt-3 (128位分组长度; CRYPTREC 推荐使用))
Hierocrypt-L1 (64位分组长度; CRYPTREC 推荐使用 (limited))
International Data Encryption Algorithm (IDEA) (64位分组长度-- 苏黎世ETH的James Massey X Lai)
Iraqi Block Cipher (IBC)
KASUMI (64位分组长度; 基于MISTY1, 被用于下一代W-CDMA cellular phone 保密)
KHAZAD (64-bit block designed by Barretto and Rijmen)
Khufu and Khafre (64位分组密码)
LION (由流密码和Hash函数构造的分组密码, by Ross Anderson)
LOKI89/91 (64位分组密码)
LOKI97 (128位分组长度的密码, AES候选者)
Lucifer (by Tuchman et al of IBM, early 1970s; modified by NSA/NBS and released as DES)
MAGENTA (AES 候选者)
Mars (AES finalist, by Don Coppersmith et al)
MISTY1 (NESSIE selection 64-bit block; Mitsubishi Electric (Japan); CRYPTREC 推荐使用 (limited))
MISTY2 (分组长度为128位: Mitsubishi Electric (Japan))
Nimbus (64位分组)
Noekeon (分组长度为128位)
NUSH (可变分组长度(64 - 256位))
Q (分组长度为128位)
RC2 64位分组,密钥长度可变.
RC6 (可变分组长度; AES finalist, by Ron Rivest et al)
RC5 (by Ron Rivest)
SAFER (可变分组长度)
SC2000 (分组长度为128位; CRYPTREC 推荐使用)
Serpent (分组长度为128位; AES finalist by Ross Anderson, Eli Biham, Lars Knudsen)
SHACAL-1 (256-bit block)
SHACAL-2 (256-bit block cypher; NESSIE selection Gemplus (France))
Shark (grandfather of Rijndael/AES, by Daemen and Rijmen)
Square (father of Rijndael/AES, by Daemen and Rijmen)
3-Way (96 bit block by Joan Daemen)
TEA(小型加密算法)(by David Wheeler Roger Needham)
Triple DES (by Walter Tuchman, leader of the Lucifer design team -- not all triple uses of DES increase security, Tuchman's does; CRYPTREC 推荐使用 (limited), only when used as in FIPS Pub 46-3)
Twofish (分组长度为128位; AES finalist by Bruce Schneier, et al)
XTEA (by David Wheeler Roger Needham)
多表代替密码机密码
Enigma (二战德国转轮密码机--有很多变种,多数变种有很大的用户网络)
紫密(Purple) (二战日本外交最高等级密码机;日本海军设计)
SIGABA (二战美国密码机,由William Friedman, Frank Rowlett, 等人设计)
TypeX (二战英国密码机)
Hybrid code/cypher combinations
JN-25 (二战日本海军的高级密码; 有很多变种)
Naval Cypher 3 (30年代和二战时期英国皇家海军的高级密码)
可视密码
有密级的 密码 (美国)
EKMS NSA的电子密钥管理系统
FNBDT NSA的加密窄带话音标准
Fortezza encryption based on portable crypto token in PC Card format
KW-26 ROMULUS 电传加密机(1960s - 1980s)
KY-57 VINSON 战术电台语音加密
SINCGARS 密码控制跳频的战术电台
STE 加密电话
STU-III 较老的加密电话
TEMPEST prevents compromising emanations
Type 1 products
破译密码
被动攻击
选择明文攻击
选择密文攻击
自适应选择密文攻击
暴力攻击
密钥长度
唯一解距离
密码分析学
中间相会攻击
差分密码分析
线性密码分析
Slide attack cryptanalysis
Algebraic cryptanalysis
XSL attack
Mod n cryptanalysis
弱密钥和基于口令的密码
暴力攻击
字典攻击
相关密钥攻击
Key derivation function
弱密钥
口令
Password-authenticated key agreement
Passphrase
Salt
密钥传输/交换
BAN Logic
Needham-Schroeder
Otway-Rees
Wide Mouth Frog
Diffie-Hellman
中间人攻击
伪的和真的随机数发生器
PRNG
CSPRNG
硬件随机数发生器
Blum Blum Shub
Yarrow (by Schneier, et al)
Fortuna (by Schneier, et al)
ISAAC
基于SHA-1的伪随机数发生器, in ANSI X9.42-2001 Annex C.1 (CRYPTREC example)
PRNG based on SHA-1 for general purposes in FIPS Pub 186-2 (inc change notice 1) Appendix 3.1 (CRYPTREC example)
PRNG based on SHA-1 for general purposes in FIPS Pub 186-2 (inc change notice 1) revised Appendix 3.1 (CRYPTREC example)
匿名通讯
Dining cryptographers protocol (by David Chaum)
匿名投递
pseudonymity
匿名网络银行业务
Onion Routing
法律问题
Cryptography as free speech
Bernstein v. United States
DeCSS
Phil Zimmermann
Export of cryptography
Key escrow and Clipper Chip
Digital Millennium Copyright Act
zh:数字版权管理;zh-tw:数位版权管理 (DRM)
Cryptography patents
RSA (now public domain}
David Chaum and digital cash
Cryptography and Law Enforcement
Wiretaps
Espionage
不同国家的密码相关法律
Official Secrets Act (United Kingdom)
Regulation of Investigatory Powers Act 2000 (United Kingdom)
术语
加密金钥
加密
密文
明文
加密法
Tabula recta
书籍和出版物
密码学相关书籍
密码学领域重要出版物
密码学家
参见List of cryptographers
密码技术应用
Commitment schemes
Secure multiparty computations
电子投票
认证
数位签名
Cryptographic engineering
Crypto systems
杂项
Echelon
Espionage
IACR
Ultra
Security engineering
SIGINT
Steganography
Cryptographers
安全套接字层(SSL)
量子密码
Crypto-anarchism
Cypherpunk
Key escrow
零知识证明
Random oracle model
盲签名
Blinding (cryptography)
数字时间戳
秘密共享
可信操作系统
Oracle (cryptography)
免费/开源的密码系统(特指算法+协议+体制设计)
PGP (a name for any of several related crypto systems, some of which, beginning with the acquisition of the name by Network Associates, have not been Free Software in the GNU sense)
FileCrypt (an open source/commercial command line version of PGP from Veridis of Denmark, see PGP)
GPG (an open source implementation of the OpenPGP IETF standard crypto system)
SSH (Secure SHell implementing cryptographically protected variants of several common Unix utilities, First developed as open source in Finland by Tatu Ylonen. There is now OpenSSH, an open source implementation supporting both SSH v1 and SSH v2 protocols. There are also commercial implementations.
IPsec (因特网协议安全IETF标准,IPv6 IETF 标准的必须的组成部分)
Free S/WAN (IPsec的一种开源实现
其它军事学分支学科
军事学概述、射击学、弹道学、内弹道学、外弹道学、中间弹道学、终点弹道学、导弹弹道学、军事地理学、军事地形学、军事工程学、军事气象学、军事医学、军事运筹学、战役学、密码学、化学战
密文是相对于明文说的,明文其实就是你要传达的消息,而明文通过加密之后就成了密文,密文其实是信息安全的一个词汇。帮你介绍一下。
信息安全的发展历史
通信保密科学的诞生
古罗马帝国时期的Caesar密码:能够将明文信息变换为人们看不懂的字符串,(密文),当密文传到伙伴手中时,又可方便的还原为原来的明文形式。 Caesar密码由明文字母循环移3位得到。
1568年,L.Battista发明了多表代替密码,并在美国南北战争期间有联军使用。例:Vigenere密码和Beaufort密码
1854年,Playfair发明了多字母代替密码,英国在第一次世界大战中使用了此密码。例:Hill密码,多表、多字母代替密码成为古典密码学的主流。
密码破译技术(密码分析)的发展:例:以1918年W.Friedman使用重合指数破译多表代替密码技术为里程碑。 1949年C.Shannon的《保密系统的通信理论》文章发表在贝尔系统技术杂志上。这两个成果为密码学的科学研究奠定了基础。从艺术变为科学。实际上,这就是通信保密科学的诞生,其中密码是核心技术。
公钥密码学革命
25年之后,20世纪70年代,IBM公司的DES(美国数据加密标准)和1976年Diffie-Hellman,提出了公开密钥密码思想,1977年公钥密码算法RSA的提出为密码学的发展注入了新的活力。
公钥密码掀起了一场革命,对信息安全有三方面的贡献:首次从计算复杂性上刻画了密码算法的强度,突破了Shannon仅关心理论强度的局限性;他将传统密码算法中两个密钥管理中的保密性要求,转换为保护其中一格的保密性及另一格的完整性的要求;它将传统密码算法中密钥归属从通信两方变为一个单独的用户,从而使密钥的管理复杂度有了较大下降。
公钥密码的提出,注意:一是密码学的研究逐步超越了数据的通信保密范围,开展了对数据的完整性、数字签名等技术的研究;二是随着计算机和网络的发展,密码学一逐步成为计算机安全、网络安全的重要支柱,使得数据安全成为信息安全的全新内容,超越了以往物理安全占据计算机安全的主导地位状态。
访问控制技术与可信计算机评估准则
1969年,B.Lampson提出了访问控制模型。
1973年,D.Bell 和L.Lapadula,创立了一种模拟军事安全策略的计算机操作模型,这是最早也是最常用的一种计算机多级安全模型。
1985年,美国国防部在Bell-Lapadula模型的基础上提出了可信计算机评估准则(通常称为橘皮书)。按照计算机系统的安全防护能力,分成8个等级。
1987年,Clark-Wilson模型针对完整性保护和商业应用提出的。
信息保障
1998年10月,美国国家安全局(NSA)颁布了信息保障技术框架1.1版,2003年2月6日,美国国防部(DOD)颁布了信息保障实施命令8500.2,从而信息保障成为美国国防组织实施信息化作战的既定指导思想。
信息保障(IA:information assurance):通过确保信息的可用性、完整性、可识别性、保密性和抵赖性来保护信息系统,同时引入保护、检测及响应能力,为信息系统提供恢复功能。这就是信息保障模型PDRR。
protect保护、detect检测、react响应、restore 恢复
美国信息保障技术框架的推进使人们意识到对信息安全的认识不要停留在保护的框架之下,同时还需要注意信息系统的检测和响应能力。
2003年,中国发布了《国家信息领导小组关于信息安全保障工作的意见》,这是国家将信息安全提到战略高度的指导性文件
信息保密技术的研究成果:
发展各种密码算法及其应用:
DES(数据加密标准)、RSA(公开密钥体制)、ECC(椭圆曲线离散对数密码体制)等。
计算机信息系统安全模型和安全评价准则:
访问监视器模型、多级安全模型等;TCSEC(可信计算机系统评价准则)、ITSEC(信息技术安全评价准则)等。
加密(Encryption)
加密是通过对信息的重新组合,使得只有收发双方才能解码并还原信息的一种手段。
传统的加密系统是以密钥为基础的,这是一种对称加密,也就是说,用户使用同一个密钥加密和解密。
目前,随着技术的进步,加密正逐步被集成到系统和网络中,如IETF正在发展的下一代网际协议IPv6。硬件方面,Intel公司也在研制用于PC机和服务器主板的加密协处理器。
身份认证(Authentication)
防火墙是系统的第一道防线,用以防止非法数据的侵入,而安全检查的作用则是阻止非法用户。有多种方法来鉴别一个用户的合法性,密码是最常用的,但由于有许多用户采用了很容易被猜到的单词或短语作为密码,使得该方法经常失效。其它方法包括对人体生理特征(如指纹)的识别,智能IC卡和USB盘。
数字签名(Digital Signature)
数字签名可以用来证明消息确实是由发送者签发的,而且,当数字签名用于存储的数据或程序时,可以用来验证数据或程序的完整性。
美国政府采用的数字签名标准(Digital Signature Standard,DSS)使用了安全哈希运算法则。用该算法对被处理信息进行计算,可得到一个160位(bit)的数字串,把这个数字串与信息的密钥以某种方式组合起来,从而得到数字签名。
内容检查(Content Inspection)
即使有了防火墙、身份认证和加密,人们仍担心遭到病毒的攻击。有些病毒通过E-mail或用户下载的ActiveX和Java小程序(Applet)进行传播,带病毒的Applet被激活后,又可能会自动下载别的Applet。现有的反病毒软件可以清除E-mail病毒,对付新型Java和ActiveX病毒也有一些办法,如完善防火墙,使之能监控Applet的运行,或者给Applet加上标签,让用户知道他们的来源。
介绍一些加密的知识
密钥加/解密系统模型
在1976年,Diffie及Hellman发表其论文“New Directions in Cryptography”[9]之前,所谓的密码学就是指对称密钥密码系统。因为加/解密用的是同一把密钥,所以也称为单一密钥密码系统。
这类算法可谓历史悠久,从最早的凯撒密码到目前使用最多的DES密码算法,都属于单一密钥密码系统。
通常,一个密钥加密系统包括以下几个部分:
① 消息空间M(Message)
② 密文空间C(Ciphertext)
③ 密钥空间K(Key)
④ 加密算法E(Encryption Algorithm)
⑤ 解密算法D(Decryption Algorithm)
消息空间中的消息M(称之为明文)通过由加密密钥K1控制的加密算法加密后得到密文C。密文C通过解密密钥K2控制的解密算法又可恢复出原始明文M。即:
EK1(M)=C
DK2(C)=M
DK2(EK1(M))=M
概念:
当算法的加密密钥能够从解密密钥中推算出来,或反之,解密密钥可以从加密密钥中推算出来时,称此算法为对称算法,也称秘密密钥算法或单密钥算法;
当加密密钥和解密密钥不同并且其中一个密钥不能通过另一个密钥推算出来时,称此算法为公开密钥算法。
1.凯撒密码变换
更一般化的移位替代密码变换为
加密:E(m)=(m+k) mod 26
解密:D(c)=(c-k) mod 26
2.置换密码
在置换密码中,明文和密文的字母保持相同,但顺序被打乱了。在简单的纵行置换密码中,明文以固定的宽度水平地写在一张图表纸上,密文按垂直方向读出;解密就是将密文按相同的宽度垂直地写在图表纸上,然后水平地读出明文。例如:
明文:encryption is the transformation of data into some unreadable form
密文:eiffob nsodml ctraee rhmtuf yeaano pttirr trinem iaota onnod nsosa
20世纪40年代,Shannon提出了一个常用的评估概念。特认为一个好的加密算法应具有模糊性和扩散性。
模糊性:加密算法应隐藏所有的局部模式,即,语言的任何识别字符都应变得模糊,加密法应将可能导致破解密钥的提示性语言特征进行隐藏;
扩散性:要求加密法将密文的不同部分进行混合,是任何字符都不在其原来的位置。
加密算法易破解的原因是未能满足这两个Shannon条件。
数据加密标准(DES)
DES算法把64位的明文输入块变为64位的密文输出块,它所使用的密钥也是64位,其功能是把输入的64位数据块按位重新组合,并把输出分为L0、R0两部分,每部分各长32位,经过16次迭代运算后。得到L16、R16,将此作为输入,进行逆置换,即得到密文输出。逆置换正好是初始置的逆运算.
具体方法 需要图 我放不上去对不起了
可以将DES算法归结如下:
子密钥生成:
C[0]D[0] = PC–1(K)
for 1 = i = 16
{C[i] = LS[i](C[i−1])
D[i] = LS[i](D[i−1])
K[i] = PC–2(C[i]D[i])}
加密过程:
L[0]R[0] = IP(x)
for 1 = i = 16
{L[i] = R[i−1]
R[i] = L[i−1] XOR f (R[i−1], K[i])}
c= IP−1(R[16]L[16])v
解密过程:
R[16]L[16] = IP(c)
for 1 = i = 16
{R[i−1] = L[i]
L[i−1] = R[i] XOR f (L[i], K[i])}
x= IP−1(L[0]R[0])
DES使用56位密钥对64位的数据块进行加密,并对64位的数据块进行16轮编码。与每轮编码时,一个48位的“每轮”密钥值由56位的完整密钥得出来。DES用软件进行解码需要用很长时间,而用硬件解码速度非常快,但幸运的是当时大多数黑客并没有足够的设备制造出这种硬件设备。
在1977年,人们估计要耗资两千万美元才能建成一个专门计算机用于DES的解密,而且需要12个小时的破解才能得到结果。所以,当时DES被认为是一种十分强壮的加密方法。 但是,当今的计算机速度越来越快了,制造一台这样特殊的机器的花费已经降到了十万美元左右,所以用它来保护十亿美元的银行间线缆时,就会仔细考虑了。另一个方面,如果只用它来保护一台服务器,那么DES确实是一种好的办法,因为黑客绝不会仅仅为入侵一个服务器而花那么多的钱破解DES密文。由于现在已经能用二十万美圆制造一台破译DES的特殊的计算机,所以现在再对要求“强壮”加密的场合已经不再适用了
DES算法的应用误区
DES算法具有极高安全性,到目前为止,除了用穷举搜索法对DES算法进行攻击外,还没有发现更有效的办法。而56位长的密钥的穷举空间为256,这意味着如果一台计算机的速度是每一秒种检测一百万个密钥,则它搜索完全部密钥就需要将近2285年的时间,可见,这是难以实现的,当然,随着科学技术的发展,当出现超高速计算机后,我们可考虑把DES密钥的长度再增长一些,以此来达到更高的保密程度。
由上述DES算法介绍我们可以看到:DES算法中只用到64位密钥中的其中56位,而第8、16、24、......64位8个位并未参与DES运算,这一点,向我们提出了一个应用上的要求,即DES的安全性是基于除了8,16,24,......64位外的其余56位的组合变化256才得以保证的。因此,在实际应用中,我们应避开使用第8,16,24,......64位作为有效数据位,而使用其它的56位作为有效数据位,才能保证DES算法安全可靠地发挥作用。如果不了解这一点,把密钥Key的8,16,24,..... .64位作为有效数据使用,将不能保证DES加密数据的安全性,对运用DES来达到保密作用的系统产生数据被破译的危险,这正是DES算法在应用上的误区,留下了被人攻击、被人破译的极大隐患。
A5 算 法
序列密码简介
序列密码又称流密码,它将明文划分成字符(如单个字母)或其编码的基本单元(如0、1),然后将其与密钥流作用以加密,解密时以同步产生的相同密钥流实现。
序列密码强度完全依赖于密钥流产生器所产生的序列的随机性和不可预测性,其核心问题是密钥流生成器的设计。而保持收发两端密钥流的精确同步是实现可靠解密的关键技术。
A5算法
A5算法是一种序列密码,它是欧洲GSM标准中规定的加密算法,用于数字蜂窝移动电话的加密,加密从用户设备到基站之间的链路。A5算法包括很多种,主要为A5/1和A5/2。其中,A5/1为强加密算法,适用于欧洲地区;A5/2为弱加密算法,适用于欧洲以外的地区。这里将详细讨论A5/1算法。
A5/1算法的主要组成部分是三个长度不同的线性反馈移位寄存器(LFSR)R1、R2和R3,其长度分别为19、22和23。三个移位寄存器在时钟的控制下进行左移,每次左移后,寄存器最低位由寄存器中的某些位异或后的位填充。各寄存器的反馈多项式为:
R1:x18+x17+x16+x13
R2:x21+x20
R3:x22+x21+x20+x7
A5算法的输入是64位的会话密钥Kc和22位的随机数(帧号)。
IDEA
IDEA即国际数据加密算法,它的原型是PES(Proposed Encryption Standard)。对PES改进后的新算法称为IPES,并于1992年改名为IDEA(International Data Encryption Algorithm)。
IDEA是一个分组长度为64位的分组密码算法,密钥长度为128位,同一个算法即可用于加密,也可用于解密。
IDEA的加密过程包括两部分:
(1) 输入的64位明文组分成四个16位子分组:X1、X2、X3和X4。四个子分组作为算法第一轮的输入,总共进行八轮的迭代运算,产生64位的密文输出。
(2) 输入的128位会话密钥产生八轮迭代所需的52个子密钥(八轮运算中每轮需要六个,还有四个用于输出变换)
子密钥产生:输入的128位密钥分成八个16位子密钥(作为第一轮运算的六个和第二轮运算的前两个密钥);将128位密钥循环左移25位后再得八个子密钥(前面四个用于第二轮,后面四个用于第三轮)。这一过程一直重复,直至产生所有密钥。
IDEA的解密过程和加密过程相同,只是对子密钥的要求不同。下表给出了加密子密钥和相应的解密子密钥。
密钥间满足:
Zi(r) ⊙ Zi(r) −1=1 mod (216+1)
−Zi(r) + Zi(r) =0 mod (216+1)
Blowfish算法
Blowfish是Bruce Schneier设计的,可以免费使用。
Blowfish是一个16轮的分组密码,明文分组长度为64位,使用变长密钥(从32位到448位)。Blowfish算法由两部分组成:密钥扩展和数据加密。
1. 数据加密
数据加密总共进行16轮的迭代,如图所示。具体描述为(将明文x分成32位的两部分:xL, xR)
for i = 1 to 16
{
xL = xL XOR Pi
xR = F(xL) XOR xR
if
{
交换xL和xR
}
}
xR = xR XOR P17
xL = xL XOR P18
合并xL 和xR
其中,P阵为18个32位子密钥P1,P2,…,P18。
解密过程和加密过程完全一样,只是密钥P1,P2,…,P18以逆序使用。
2. 函数F
把xL分成四个8位子分组:a, b, c 和d,分别送入四个S盒,每个S盒为8位输入,32位输出。四个S盒的输出经过一定的运算组合出32位输出,运算为
F(xL) =((S1,a + S2,b mod 232) XOR S3,c) + S4,d mod 232
其中,Si,x表示子分组x(x=a、b、c或d)经过Si (i=1、2、3或4)盒的输出。
没有太多地方写了,不把整个过程列上面了,就简单介绍一下好了。
GOST算法
GOST是前苏联设计的分组密码算法,为前苏联国家标准局所采用,标准号为:28147–89[5]。
GOST的消息分组为64位,密钥长度为256位,此外还有一些附加密钥,采用32轮迭代。
RC5算法
RC5是一种分组长度、密钥长度和加密迭代轮数都可变的分组密码体制。RC5算法包括三部分:密钥扩展、加密算法和解密算法。
PKZIP算法
PKZIP加密算法是一个一次加密一个字节的、密钥长度可变的序列密码算法,它被嵌入在PKZIP数据压缩程序中。
该算法使用了三个32位变量key0、key1、key2和一个从key2派生出来的8位变量key3。由密钥初始化key0、key1和key2并在加密过程中由明文更新这三个变量。PKZIP序列密码的主函数为updata_keys()。该函数根据输入字节(一般为明文),更新三个32位的变量并获得key3。
重点:单向散列函数
MD5 算 法
md5的全称是message- digest algorithm 5(信息-摘要算法),在90年代初由mit laboratory for computer science和rsa data security inc的ronald l. rivest开发出来,经md2、md3和md4发展而来。它的作用是让大容量信息在用数字签名软件签署私人密匙前被"压缩"成一种保密的格式(就是把一 个任意长度的字节串变换成一定长的大整数)。不管是md2、md4还是md5,它们都需要获得一个随机长度的信息并产生一个128位的信息摘要。虽然这些 算法的结构或多或少有些相似,但md2的设计与md4和md5完全不同,那是因为md2是为8位机器做过设计优化的,而md4和md5却是面向32位的电 脑。
rivest在1989年开发出md2算法。在这个算法中,首先对信息进行数据补位,使信息的字节长度是16的倍数。然后,以一个16位的检验和追加到 信息末尾。并且根据这个新产生的信息计算出散列值。后来,rogier和chauvaud发现如果忽略了检验和将产生md2冲突。md2算法的加密后结果 是唯一的--既没有重复。 为了加强算法的安全性,rivest在1990年又开发出md4算法。md4算法同样需要填补信息以确 保信息的字节长度加上448后能被512整除(信息字节长度mod 512 = 448)。然后,一个以64位二进制表示的信息的最初长度被添加进来。信息被处理成512位damg?rd/merkle迭代结构的区块,而且每个区块要 通过三个不同步骤的处理。den boer和bosselaers以及其他人很快的发现了攻击md4版本中第一步和第三步的漏洞。dobbertin向大家演示了如何利用一部普通的个人电 脑在几分钟内找到md4完整版本中的冲突(这个冲突实际上是一种漏洞,它将导致对不同的内容进行加密却可能得到相同的加密后结果)。毫无疑问,md4就此 被淘汰掉了。 尽管md4算法在安全上有个这么大的漏洞,但它对在其后才被开发出来的好几种信息安全加密算法的出现却有着不可忽视的引导作用。除了md5以外,其中比较有名的还有sha-1、ripe-md以及haval等。
一年以后,即1991年,rivest开发出技术上更为趋近成熟的md5算法。它在md4的基础上增加了"安全-带子"(safety-belts)的 概念。虽然md5比md4稍微慢一些,但却更为安全。这个算法很明显的由四个和md4设计有少许不同的步骤组成。在md5算法中,信息-摘要的大小和填充 的必要条件与md4完全相同。den boer和bosselaers曾发现md5算法中的假冲突(pseudo-collisions),但除此之外就没有其他被发现的加密后结果了。 van oorschot和wiener曾经考虑过一个在散列中暴力搜寻冲突的函数(brute-force hash function),而且他们猜测一个被设计专门用来搜索md5冲突的机器(这台机器在1994年的制造成本大约是一百万美元)可以平均每24天就找到一 个冲突。但单从1991年到2001年这10年间,竟没有出现替代md5算法的md6或被叫做其他什么名字的新算法这一点,我们就可以看出这个瑕疵并没有 太多的影响md5的安全性。上面所有这些都不足以成为md5的在实际应用中的问题。并且,由于md5算法的使用不需要支付任何版权费用的,所以在一般的情 况下(非绝密应用领域。但即便是应用在绝密领域内,md5也不失为一种非常优秀的中间技术),md5怎么都应该算得上是非常安全的了。
算法
MD表示消息摘要(Message Digest)。MD5是MD4的改进版,该算法对输入的任意长度消息产生128位散列值(或消息摘要。MD5算法可用图4-2表示。
对md5算法简要的叙述可以为:md5以512位分组来处理输入的信息,且每一分组又被划分为16个32位子分组,经过了一系列的处理后,算法的输出由四个32位分组组成,将这四个32位分组级联后将生成一个128位散列值。
1) 附加填充位
首先填充消息,使其长度为一个比512的倍数小64位的数。填充方法:在消息后面填充一位1,然后填充所需数量的0。填充位的位数从1~512。
2) 附加长度
将原消息长度的64位表示附加在填充后的消息后面。当原消息长度大于264时,用消息长度mod 264填充。这时,消息长度恰好是512的整数倍。令M[0 1…N−1]为填充后消息的各个字(每字为32位),N是16的倍数。
3) 初始化MD缓冲区
初始化用于计算消息摘要的128位缓冲区。这个缓冲区由四个32位寄存器A、B、C、D表示。寄存器的初始化值为(按低位字节在前的顺序存放):
A: 01 23 45 67
B: 89 ab cd ef
C: fe dc ba 98
D: 76 54 32 10
4) 按512位的分组处理输入消息
这一步为MD5的主循环,包括四轮,如图4-3所示。每个循环都以当前的正在处理的512比特分组Yq和128比特缓冲值ABCD为输入,然后更新缓冲内容。
四轮操作的不同之处在于每轮使用的非线性函数不同,在第一轮操作之前,首先把A、B、C、D复制到另外的变量a、b、c、d中。这四个非线性函数分别为(其输入/输出均为32位字):
F(X,Y,Z) = (XY)((~X) Z)
G(X,Y,Z) = (XZ)(Y(~Z))
H(X,Y,Z) = XYZ
I(X,Y,Z) = Y(X(~Z))
其中,表示按位与;表示按位或;~表示按位反;表示按位异或。
此外,由图4-4可知,这一步中还用到了一个有64个元素的表T[1..64],T[i]=232×abs(sin(i)),i的单位为弧度。
根据以上描述,将这一步骤的处理过程归纳如下:
for i = 0 to N/16−1 do
/* 每次循环处理16个字,即512字节的消息分组*/
/*把第i个字块(512位)分成16个32位子分组拷贝到X中*/
for j = 0 to 15 do
Set X[j] to M[i*16+j]
end /*j 循环*/
/*把A存为AA,B存为BB,C存为CC,D存为DD*/
AA = A
BB = B
CC = C
DD = D
/* 第一轮*/
/* 令[abcd k s i]表示操作
a = b + ((a + F(b,c,d) + X[k] + T[i]) s)
其中,Ys表示Y循环左移s位*/
/* 完成下列16个操作*/
[ABCD 0 7 1 ] [DABC 1 12 2 ] [CDAB 2 17 3 ] [BCDA 3 22 4 ]
[ABCD 4 7 5 ] [DABC 5 12 6 ] [CDAB 6 17 7 ] [BCDA 7 22 8 ]
[ABCD 8 7 9 ] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]
[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]
/* 第二轮*/
/*令[abcd k s i]表示操作
a = b + ((a + G(b,c,d) + X[k] + T[i]) s)*/
/*完成下列16个操作*/
[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]
[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]
[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]
[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]
/*第三轮*/
/*令[abcd k s t]表示操作
a = b + ((a + H(b,c,d) + X[k] + T[i]) s)*/
/*完成以下16个操作*/
[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]
[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]
[ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]
/*第四轮*/
/*令[abcd k s t]表示操作
a = b + ((a + I(b,c,d) + X[k] + T[i]) s) */
/*完成以下16个操作*/
[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]
[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]
[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]
[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]
A = A + AA
B = B + BB
C = C + CC
D = D + DD
end /*i循环*/
5) 输出
由A、B、C、D四个寄存器的输出按低位字节在前的顺序(即以A的低字节开始、D的高字节结束)得到128位的消息摘要。
以上就是对MD5算法的描述。MD5算法的运算均为基本运算,比较容易实现且速度很快。
安全散列函数(SHA)
算法
SHA是美国NIST和NSA共同设计的安全散列算法(Secure Hash Algorithm),用于数字签名标准DSS(Digital Signature Standard)。SHA的修改版SHA–1于1995年作为美国联邦信息处理标准公告(FIPS PUB 180–1)发布[2]。
古典密码是密码学的源头。这一时期的密码是一种艺术,还算不上是一门学科。密码学家常常是凭借直觉和信念来进行密码设计和分析,而不是推理证明。
古典密码的两个主要体制是代换密码和置换密码。代换密码采用一个代换表,将一段明文变换成一段密文,这个代换表就是密钥。如果代换表只有一个,则代换过程被称为单表代换。如果代换表多于一个,则代换过程被称为多表代换。置换密码是一种特殊的代换密码,置换密码变换过程不改变明文字母,只改变它们的位置。
单表代换密码的一个典型代表是仿射密码。仿射密码的加密变换可以表示为 Ek(i)=(ik1+k) mod N,其中密钥k = (k1,k),N为明文字表大小,i为明文,k与N互素。当k=0时的变换称为乘法密码;当k1=1时的变换称为加法密码。
“恺撒密码”是一种典型的加法密码,这种密码曾经被罗马帝国的恺撒大帝频繁用于战争通信,因此称为“恺撒密码”。下面举例描述一下恺撒密码。假定密钥 k =(1,11),明文消息为“i am nine”,N = 26。密钥k =(1,11)确定了密码代换表中明文字母“a”将被替换成“l”,字母“b”将被替换成“m”,依此类推。整个代换过程描述如表1所示。对于英文字母表,恺撒密码的密钥取值范围只有25(不包括k为0的情形),即只能构造出25种不同的明密文代换表。因此,恺撒密码很容易被穷举破译。
为了进一步提高密码强度,在单表代换的基础上,又进一步提出了多表代换。多表代换密码是以多个代换表依次对明文消息的字母进行代换的加密方法。多表代换密码的典型代表是维吉尼亚密码,它是以16世纪法国外交官 Blaise deVigen è re的名字命名的。
维吉尼亚密码是一种以位移代换为基础的周期代换密码,其中代换表的数目为d,d代换表由d个字母序列确定的密钥决定。我们在前面例子的基础上,再以格的形式解释维吉尼亚密码的代换过程,具体加密代换过程如表2所示。明文信息为“i am nine i feel very good”,代换表数目d = 6,密钥k = cipher,密钥对应的数数序列为k =(2,8,15,7,4,17)。将密钥整数序列与明文序列周期性的模26“相加”,即可得到密文整数序列,进而可以变换成密文。
恺撒密码和维吉尼亚密码都是以单个字母为代换对象的。如果每次对多于1个字母进行代换就是多字母代换,多字母代换更加有利于隐藏字母的自然频度,从而更有利于抵抗统计分析。
置换密码的典型代表是栅栏密码。栅栏密码出现于1861年至1865年的美国南北战争时期。其加密原理是:明文按列写入,密文按行输出。加密过程可以使用个置换也可以使用多个置换。与代换密码相比,置换密码可以打破消息中的某些固定结构模式,这个优点被融入到现代密码算法的设计中。
古典密码在对抗密码分析方面有较大不足。密码分析学的主要目标是研究加密消息的破译或消息的伪造。密码系统安全的一个必要条件是密钥空间足够大,能够有效地应对穷举密钥搜索攻击,但密钥空间足够大不是密码系统安全的充分条件。古典密码在统计特性方面存在安全缺陷。在单表代换下,字母的频度、重复字母模式字母结合方式等统计特性,除了字母符号发生了改变外,都没有发生改变,这些统计特性可以用于密码破译。多表代换下,明文的统计特性通过多个表的平均作用被隐蔽起来,但是用重合指数法等分析方法可以很容易地确定维吉尼亚密码密钥长度,再用攻击单表代换的方法确定密钥字。已有事实证明,用唯密文攻击法(攻击者只拥有一个或者多个用同一个密钥加密的密文)分析单表和多表代换密码是可行的,因此,以上古典密码都是不安全的。
数观天下作为“最懂甲方的密码行业咨询媒体”,会提供更多甲方思路、理念及项目情况,为产业提供桥梁,促进密码与应用完美结合
古典密码学之所以被称为古典,是因为区别于现代密码学,这些密码理论虽然很有价值,但是现在很少使用。因此,学习古典密码学,主要是学习前人设计密码的思路,和他们成功或失败的历史。
为了较好地为信息加密,古人发明了加密算法: 维吉尼亚密码(Vigenère Cipher) 。其特点就是选用某一段字符串作为其密钥,并将密钥重复若干次直到长度与明文相同。
例如,用密钥“THINK”加密明文"ATTACKATONCE",就要将密钥重复并得到密钥排列"THINKTHINKTH"。密钥排列得到的一串字符,每个字符都代表将该位置的明文字母向后移动某位,从而得到密文。对于上述的"THINKTHINKTH"而言,用所需移位的数字表示就是“19,7,8,13,10,19,7,8,13,10,19,7”。
明文第一位(A)对应密钥排列的第一位(T),而T在字母表中排第19位(A是第0位),就将明文的第一位字母(A)向字母表排序的后面移动19位,由于A在字母表中排第0位,移动完是第19位T,因此得到密文第一位字母(T);
明文的第二位(T)对应密钥排列的第二位(H),而H在字母表中排第7位,就将明文的第二位字母(T)向字母表排序的后面移动7位,由于T是第19位,19向后7位是第26位,而字母表中最后一位字母Z是第25位,因此得到新的循环中的字母表第0位,于是得到密文的第二位字母(A);
第三位同理能够得到字母表中第27位,也就是B。以此类推,最终将会得到密文"TABNMDHBBXVL"。
相较于逻辑推演生成密码,维吉尼亚密码还可以使用表格法生成密码。
如下图,对于明文的第三个字母T,对应密钥的第三个字母I,于是使用表格中I行字母表进行加密,得到密文第三个字母B。类似地,明文第六个字母为K,对应密钥的第六个字母T,在表格中使用对应的T行进行加密,得到密文第二个字母D。以此类推,可以得到密文“TABNMDHBBXVL”。
可以看出,使用表格法无论是加密还是解密,都有着更低的学习成本以及更高的效率。这种密码的高易用性和不错的强度让它声名显赫。
对包括维吉尼亚密码在内的所有多表密码的破译,都是以字母的出现频率为基础的,但直接的频率分析却并不适用。例如,如果’P‘是密文中出现次数最多的字母,则’P‘所代表的明文很有可能是’E‘(在明文为英文的前提下),其原因在本文的第二章已经论述。由于在维吉尼亚密码中,同一个明文字母可以被加密成不同的密文,因而简单的频率分析在这里并没有用。
然而,维吉尼亚密码也有着很明显的漏洞。如果我们知道了密钥的长度,那密文就可以被看作是交织在一起的恺撒密码,而其中每一个都可以单独破解。例如,上个例子中以”THINKTHINKTH“作为密钥排列,这种情况下明文的第一位和第六位都将以密钥字母’T‘加密,它们的偏移量就是相同的。倘若明文足够长,就可以选取所有模5同余的位上得到字母来组成一组恺撒密码。
因此,对于一个明文足够长、密钥长度为t的维吉尼亚密码,至多需要将其按照模t同余的原则分解为t组平移密码即可破译。于是,破译过程的核心便落在了如何取得t值上。
为了求出密钥长度t,可以利用卡西斯基实验和重合指数。卡西斯基实验的内容很容易理解,不多做赘述。这里引用 百度百科 中的例子。
除了卡西斯基实验,我们也可以使用别的参数来描述猜测的t值是否准确。当计算某个密文的 重合指数 (又名: 重合概率 , Index of Coincidence )时,即相当于求在某个密文中随机无放回地抽取其中的两位,这两位的字母相同的概率。
对于一个由任意字母表所构成的密文字母串而言,其重合指数可以表示下图:
其中 c 是归一化系数,用于对不同字母表进行归一化处理(英语为26), n 下标 a是字母“a”出现在文本中的次数, N 是文本的长度。重合指数也可以用求和的形式来表示:
我们已经知道,维吉尼亚密码可以被分解为若干组平移密码来破译,而一个明文足够长的平移密码的重合指数接近0.0687。换言之,如果我们选取某个t值,使得分组后的密文的重合指数接近0.065,则说明选取的t值与密钥的长度是一致的。
这里引用 维基百科 中的例子进一步阐述,为简化描述,下文中“重合指数”全部指明文为英文时的情况:
作为使用IC的实际例子,假设我们截获了以下密文消息:
(分为五个字符只是一个 电报 惯例,与实际字长无关。)我们怀疑这是一个使用 Vigenère密码 加密的英文密文,其中包含普通的A-Z分量和一个短的重复关键字,我们可以考虑密文“堆叠”成若干列,例如7列:
如果密钥大小恰好与假定的列数相同,那么单个列中的所有字母都将使用相同的密钥字母加密,实际上是一个简单的恺撒密码,应用于随机选择的英文明文字符。与它们相应的密文字母组,尽管每个字母已被置换(移位对应于密钥字母的量,参考本文第四节),也应具有类似于英语的频率分布的粗糙度。
因此,如果我们计算每列重合指数IC,它应该在0.067左右;另一方面,如果我们猜错了密钥大小(也就是选错了列数),则其重合指数IC应该在0.0385左右。因此,我们分别计算当密钥大小从1到10时的 IC:
从上图可以看出,密钥长度t很可能是5.如果实际长度是5,那么当长度取10的时候也会有较高的IC,原因是此时它的每列也对应一个简单的恺撒加密。
在求得密钥长度之后,通过穷举密钥字母的每一种可能取值(A到Z总共26种),并且针对每一行求其在某一取值下重合指数,重合指数最高的情况下该行最有可能为明文原文,此时的穷举结果即为密钥字母。以下是经过解密后得到的明文:
从中可以读出明文想要发送的信息为:
在明显的位置恢复了单词划分。“ XX”显然是“空”字符,用于填充最后一组进行传输。
整个过程可以很容易地打包成自动算法来破解这些密码。由于正常的统计波动,这种算法偶尔会做出错误的选择,特别是在分析短密文时。
主要分三个阶段!
密码学是一个即古老又新兴的学科。密码学(Cryptology)一字源自希腊文"krypto's"及"logos"两字,直译即为"隐藏"及"讯息"之意。密码学有一个奇妙的发展历程,当然,密而不宣总是扮演主要角色。所以有人把密码学的发展划分为三个阶段:
第一阶段为从古代到1949年。这一时期可以看作是科学密码学的前夜时期,这阶段的密码技术可以说是一种艺术,而不是一种科学,密码学专家常常是凭知觉和信念来进行密码设计和分析,而不是推理和证明。
早在古埃及就已经开始使用密码技术,但是用于军事目的,不公开。
1844年,萨米尔·莫尔斯发明了莫尔斯电码:用一系列的电子点划来进行电报通讯。电报的出现第一次使远距离快速传递信息成为可能,事实上,它增强了西方各国的通讯能力。
20世纪初,意大利物理学家奎里亚摩·马可尼发明了无线电报,让无线电波成为新的通讯手段,它实现了远距离通讯的即时传输。马可尼的发明永远地改变了密码世界。由于通过无线电波送出的每条信息不仅传给了己方,也传送给了敌方,这就意味着必须给每条信息加密。
随着第一次世界大战的爆发,对密码和解码人员的需求急剧上升,一场秘密通讯的全球战役打响了。
在第一次世界大战之初,隐文术与密码术同时在发挥着作用。在索姆河前线德法交界处,尽管法军哨兵林立,对过往行人严加盘查,德军还是对协约国的驻防情况了如指掌,并不断发动攻势使其陷入被动,法国情报人员都感到莫名其妙。一天,有位提篮子的德国农妇在过边界时受到了盘查。哨兵打开农妇提着的篮子,见里头都是煮熟的鸡蛋,亳无可疑之处,便无意识地拿起一个抛向空中,农妇慌忙把它接住。哨兵们觉得这很可疑,他们将鸡蛋剥开,发现蛋白上布满了字迹,都是英军的详细布防图,还有各师旅的番号。原来,这种传递情报的方法是德国一位化学家提供的,其作法并不复杂:用醋酸在蛋壳上写字,等醋酸干了后,再将鸡蛋煮熟,字迹便透过蛋壳印在蛋白上,外面却没有任何痕迹。
1914年8月5日,英国“泰尔哥尼亚”号船上的潜水员割断了德国在北大西洋海下的电缆。他们的目的很简单,就是想让德国的日子更难过,没想到这却使德方大量的通讯从电缆转向了无线电。结果,英方截取了大量原本无法得到的情报。情报一旦截获,就被送往40号房间——英国海军部的密件分析部门。40号房间可以说是现代密件分析组织的原型,这里聚集了数学家、语言学家、棋类大师等任何善于解谜的人。
1914年9月,英国人收到了一份“珍贵”的礼物:同盟者俄国人在波罗的海截获了一艘德国巡洋舰“玛格德伯格”号,得到一本德国海军的密码本。他们立即将密码本送至40号房间,允许英国破译德国海军的密件,并在战争期间围困德军战船。能够如此直接、顺利且经常差不多是同时读取德国海军情报的情况,在以往的战事中几乎从未发生过。
密码学历史上最伟大的密码破译事件开始于1917年1月17日。当时英军截获了一份以德国最高外交密码0075加密的电报,这个令人无法想象的系统由一万个词和词组组成,与一千个数字码群对应。密电来自德国外交部长阿瑟·齐麦曼,传送给他的驻华盛顿大使约翰·冯·贝伦朵尔夫,然后继续传给德国驻墨西哥大使亨尼希·冯·艾克哈尔特,电文将在那里解密,然后交给墨西哥总统瓦律斯提阿诺·加汉扎。
密件从柏林经美国海底电缆送到了华盛顿,英军在那里将其截获并意识到了它的重要性。但是,同样接到密件的约翰·冯·贝伦朵尔夫却在他的华盛顿办公室里犯了个致命的错误:他们将电报用新的0075密件本译出,然后又用老的密件本加密后用电报传送到墨西哥城。大使先生没有意识到,他已经犯下了一个密码使用者所能犯的最愚蠢的、最可悲的错误。
此时,已经破译了老密码的英方正对着这个未曾破译的新外交密码系统一筹莫展,不过没过多久,他们便从大使先生的糊涂操作中获得了新旧密码的比较版本。随着齐麦曼的密件逐渐清晰起来,其重要性令人吃惊。
尽管1915年美国的远洋客轮“露斯塔尼亚”号被德军击沉,但只要德国对其潜艇的行动加以限制,美国仍将一直保持中立。齐麦曼的电文概括了德国要在1917年2月1日重新开始无限制海战以抑制英国的企图。为了让美国原地不动,齐麦曼建议墨西哥入侵美国,重新宣布得克萨斯州、新墨西哥州和亚里桑纳州归其所有。德国还要墨西哥说服日本进攻美国,德国将提供军事和资金援助。
英国海军部急于将破译的情报通知美国而又不能让德国知道他们的密码已被破译。于是,英国的一个特工成功地渗入了墨西哥电报局,得到了送往墨西哥总统的解了密的文件拷贝。这样,秘密就可能是由墨西哥方泄露的,他们以此为掩护将情报透露给了美国。
美国愤怒了。每个人都被激怒了,原先只是东海岸的人在关心,现在,整个中西部都担心墨西哥的举动。电文破译后六个星期,美国对德国宣战。当总统伍德罗·威尔逊要求对德宣战时,站在他背后的,是一个团结起来的愤怒的国家,它时刻准备对德作战。
这可能是密码破译史上,当然也是情报史上最著名的事件。齐麦曼的电文使整个美国相信德国是国家的敌人。德国利用密码破译击败了俄军,反过来又因自己的密码被破译而加速走向了灭亡。
第一次世界大战前,重要的密码学进展很少出现在公开文献中。直到1918年,二十世纪最有影响的密码分析文章之一¾¾William F. Friedman的专题论文《重合指数及其在密码学中的应用》作为私立的“河岸(Riverbank)实验室”的一份研究报告问世了,其实,这篇著作涉及的工作是在战时完成的。一战后,完全处于秘密工作状态的美国陆军和海军的机要部门开始在密码学方面取得根本性的进展。但是公开的文献几乎没有。
然而技术却在飞速的发展,简单的明文字母替换法已经被频率分析法毫无难度地破解了,曾经认为是完美的维吉耐尔(Vigenere)密码和它的变种也被英国人Charles Babbage破解了。顺便说一句,这个Charles Babbage可不是凡人,他设计了差分机Difference Engine和分析机Analytical Engine,而这东西就是现在计算机的先驱。这个事实给了人们两个启示:第一,没有哪种“绝对安全”的密码是不会被攻破的,这只是个时间问题;第二,破译密码看来只要够聪明就成。在二次大战中,密码更是扮演一个举足轻重的角色,许多人认为同盟国之所以能打赢这场战争完全归功於二次大战时所发明的破译密文数位式计算机破解德日密码。
1918年,加州奥克兰的Edward H.Hebern申请了第一个转轮机专利,这种装置在差不多50年里被指定为美军的主要密码设备,它依靠转轮不断改变明文和密文的字母映射关系。由于有了转轮的存在,每转动一格就相当于给明文加密一次,并且每次的密钥不同,而密钥的数量就是全部字母的个数――26个。
同年,密码学界的一件大事“终于”发生了:在德国人Arthur Scherbius天才的努力下,第一台非手工编码的密码机――ENIGMA密码机横空出世了。密码机是德军在二战期间最重要的通讯利器,也是密码学发展史上的一则传奇。当时盟军借重英国首都伦敦北方布莱奇利公园的「政府电码与密码学院」,全力破译德军之「谜」。双方隔著英吉利海峡斗智,写下一页精彩无比的战史,后来成为无数电影与影集的主要情节,「猎杀U571」也是其中之一。
随着高速、大容量和自动化保密通信的要求,机械与电路相结合的转轮加密设备的出现,使古典密码体制也就退出了历史舞台。
第二阶段为从1949年到1975年。
1949年仙农(Claude Shannon)《保密系统的通信理论》,为近代密码学建立了理论基础。从1949年到1967年,密码学文献近乎空白。许多年,密码学是军队独家专有的领域。美国国家安全局以及前苏联、英国、法国、以色列及其它国家的安全机构已将大量的财力投入到加密自己的通信,同时又千方百计地去破译别人的通信的残酷游戏之中,面对这些政府,个人既无专门知识又无足够财力保护自己的秘密。
1967年,David Kahn《破译者》(The CodeBreaker)的出现,对以往的密码学历史作了相当完整的记述。《破译者》的意义不仅在于涉及到相当广泛的领域,它使成千上万的人了解了密码学。此后,密码学文章开始大量涌现。大约在同一时期,早期为空军研制敌我识别装置的Horst Feistel在位于纽约约克镇高地的IBM Watson实验室里花费了毕生精力致力于密码学的研究。在那里他开始着手美国数据加密标准(DES)的研究,到70年代初期,IBM发表了Feistel和他的同事在这个课题方面的几篇技术报告。
第三阶段为从1976年至今。1976年diffie 和 hellman 发表的文章“密码学的新动向”一文导致了密码学上的一场革命。他们首先证明了在发送端和接受端无密钥传输的保密通讯是可能的,从而开创了公钥密码学的新纪元。
1978年,R.L.Rivest,A.Shamir和L.Adleman实现了RSA公钥密码体制。
1969年,哥伦比亚大学的Stephen Wiesner首次提出“共轭编码”(Conjugate coding)的概念。1984年,H. Bennett 和G. Brassard在次思想启发下,提出量子理论BB84协议,从此量子密码理论宣告诞生。其安全性在于:1、可以发现窃听行为;2、可以抗击无限能力计算行为。
1985年,Miller和Koblitz首次将有限域上的椭圆曲线用到了公钥密码系统中,其安全性是基于椭圆曲线上的离散对数问题。
1989年R.Mathews, D.Wheeler, L.M.Pecora和Carroll等人首次把混沌理论使用到序列密码及保密通信理论,为序列密码研究开辟了新途径。
2000年,欧盟启动了新欧洲数据加密、数字签名、数据完整性计划NESSIE,究适应于21世纪信息安全发展全面需求的序列密码、分组密码、公开密钥密码、hash函数以及随机噪声发生器等技术。
建议你可以参考下:密码学基础、密码学原理、OpenSSL等书籍