网站锚点,百度公司图片,网站换模板,查域名价格密码学是数学上的一个分支#xff0c;同时也是计算机安全方向上很重要的基础原理#xff0c;设置密码的目的是保证信息的机密性、完整性和不可抵赖性#xff0c;安全方向上另外的功能——可用性则无法保证#xff0c;可用性有两种方案保证#xff0c;冗余和备份#xff0…密码学是数学上的一个分支同时也是计算机安全方向上很重要的基础原理设置密码的目的是保证信息的机密性、完整性和不可抵赖性安全方向上另外的功能——可用性则无法保证可用性有两种方案保证冗余和备份有关特性可见信息安全五大特性。
密码的发展也已由来已久最早的密码可追溯到罗马时期计算机诞生前的密码学都称为古典密码现代密码则分为对称加密和非对称加密两两种根本区别是解密使用的密钥对称加密使用同一个密钥进行加密解密非对称加密使用公钥加密私钥解密本文将对主流的算法进行简单介绍基础概念可见密码算法的概念
古典密码
相关背景和知识也蛮有意思基本是古代希腊和罗马时因为行政和战争的需要发展而来详细可见该密码学发展简史和古典密码算法。
数学算法上的最早加密方法是凯撒加密采用字母后移k位的方法生成密文数学表示位akm这种方法如果知道原理其实只要暴力26次就破解了。
仿射密码采用移位密码和乘数密码的组合字母在移位前先乘一个数数学表示位axb(mod 26)m解密过程涉及逆元计算仅作了解即可详细方法见仿射密码。
弗吉尼亚密码是凯撒的改进使用一个字符串进行加密如code分别对应字母位置3 15 4 5字母循环与这四个值相加加密。该方法的密钥破解有些困难但因为密钥固定而统计分析上句子出现字母频率的排序大致固定如最常出现的是字母e若统计中一个字母出现此处最多则可推断其为e。但因为循环加密特定字母的统计信息没有决定性作用此时也可以通过词频统计详细破解方法可见弗吉尼亚原理及破解。
对称密码
随着计算机的诞生算力极大增强古典密码用人手工来算可能很麻烦但就几十上百种可能性对计算机来说实在是洒洒水所以产生了保密性更强的对称密码。
DES—数据加密标准
Data Encryption Standard即数据加密标准是一种使用密钥加密的块算法。与流密码逐字节加密类似DES是分组加密的应用即将明文分成字节块分别加密后再组合。
DES设计中使用了分组密码设计的两个原则混淆confusion和扩散(diffusion)其目的是抗击敌手对密码系统的统计分析。混淆是使密文的统计特性与密钥的取值之间的关系尽可能复杂化以使密钥和明文以及密文之间的依赖性对密码分析者来说是无法利用的。扩散的作用就是将每一位明文的影响尽可能迅速地作用到较多的输出密文位中以便在大量的密文中消除明文的统计结构并且使每一位密钥的影响尽可能迅速地扩展到较多的密文位中以防对密钥进行逐段破译。
DES将数据分为64位的数据块与64位的密钥进行运算加密大致流程图如下 各步流程为 1明文经过IP表置换扩散 2分为32位的 L 0 L_0 L0和 R 1 R_1 R1 3 L 1 R 0 L_1R_0 L1R0 R 1 L 0 与 R 0 加密结果的异或 R_1L_0与R_0加密结果的异或 R1L0与R0加密结果的异或 4上述过程重复16次实现混淆目的 5获得 L 1 6 和 R 1 6 L_16和R_16 L16和R16 6IP表逆置换获得密文。
详细说明如下
明文首先经过IP置换打乱原有顺序即将对应序列的值移动到表的位置置换表与逆置换表如下 加密F函数过程如下 1E扩展将32位的数据扩展为48位 将32位数据分成8组每行四位每组的前后分别加上该位的上一个字符和下一个字符就是增加两列如图所示 2与48位的密钥异或运算 3经S盒压缩数据到32位 将数据分为8块每块6位数据6进4出每块的头尾两个数转化成十进制数作为列数中间四个数转化为十进制数作为行数到S盒中对应查找转化S盒有8个进一步增加了保密性S1盒如下图 这一步是算法中唯一非线性的最直接的扩散手段。 4P盒置换32位到32位是再一次的混淆盒扩散过程。 再与L异或生成新的R。
最后讲密钥是如何生成的64位密钥56位参与运算8位校验位分别为81624324864如何获取56位参与运算 56位密钥先经过PC1表置换打乱顺序前28为作为 C C C后28为作为 D D D然后移位具体不记得了但也无伤大雅再使用PC2表从56位中选48位用于运算。
DES折腾这么多遍这表那表的总结起来其实就是两个目的 1增加密钥复杂性减少与密文关联性。又算又选的让攻击者很难推出具体是那些数字受影响了从而也就无法从密钥入手破解密文 2减少统计分析特征。不断从盒里选取匹配规则明文多次打乱顺序重新组合为的就是避免被统计分析猜出可能的字母或单词减少统计分析破解的可能。
使用在线网站加密输出如下 该部分详细内容可见DES核心内容。
AES—高级加密标准
在DES已经被证明不安全的情境下创造出来替代DES的也说明到目前为止AES还是安全的。
该分组密码算法需要明文长度128密钥长度可以是128、192和256分别需要进行10、12、14轮计算。该算法将128位明文分成4×4的矩阵每个块内8位明文经过初始变换后经过9轮循环(字节代换、行移位、列混合、轮密钥加)最后再经过一轮计算(字节代换、行移位、轮密钥加)后就输出密文大致流程图如下 下面对一些操作详细讲解 1初始变换。只需要将明文与密文进行异或操作。 2字节代换。S盒代换每个块内8位数据高4位作为行低4位作为列在S盒对应位置替换。 3行移位。左循环移位第一行不变第二行左移一位第三行左移两位第四行左移三位。 4列混合也称列混淆。该部分是AES中最复杂的部分左乘一个给定矩阵但该乘法部署矩阵点积运算而是基于有限域的计算方法将点积运算中的改为异或操作×转为二进制即 00000010 ∗ ( a 7 , a 6 . . . a 0 ) 00000010*(a_7,a_6...a_0) 00000010∗(a7,a6...a0)结果为分段函数当 a 6 a 5 . . a 0 0 a 7 0 a_6a_5..a_00a_70 a6a5..a00a70 ( a 6 a 5 . . a 0 0 ) 异或 ( 00000010 ) , a 7 1 (a_6a_5..a_00)异或(00000010),a_71 (a6a5..a00)异或(00000010),a71 5轮密钥加。该部分主要涉及轮密钥的生成步骤即由密钥生成10轮密钥。 原密钥分为 w 0 , w 1 , w 2 , w 3 w_0,w_1,w_2,w_3 w0,w1,w2,w3四个列计算新的 w i w_i wi使用 w [ i ] w [ i − 4 ] 异或 w [ i − 1 ] 当 i 不是 4 的倍数即 w 5 w 1 异或 w 4 w_{[i]}w_{[i-4]}异或w_{[i-1]}当i不是4的倍数即w_5w_1异或w_4 w[i]w[i−4]异或w[i−1]当i不是4的倍数即w5w1异或w4当 i 是四的倍数 w [ i ] w [ i − 4 ] 异或 T ( w [ i − 1 ] ) i是四的倍数w_{[i]}w[i-4]异或T(w[i-1]) i是四的倍数w[i]w[i−4]异或T(w[i−1])其中T函数又分为如下步骤 字循环4个字节上移一个字节 字节代换即S盒代换 常量异或给定常量的第j列进行异或j为当前进行的第j轮。
到此AES密文就可以生成了更多详细内容可见AES加密算法写的真的hin好。
同样在线工具生成如图
非对称加密
现在更强更神奇的算法是公钥加密私钥解密这种算法强度高无需交换密钥但是效率实在很低比对称加密可能要慢一百倍所以一般仅用于数字签名和密钥交换等领域。
密钥交换协议Diffie-Hellman
对称加密确实已经能保证安全了但二者的密钥如何确定呢密钥作为信息如果要在网上传递如何保证安全再设置密钥保护吗那这问题就没完没了我猜是为了解决该问题诞生了非对称加密。
非对称加密的图示如下 二者公开选取素数q和原根a并各自选取私钥 X A 和 X B X_A和X_B XA和XBalice计算 Y A a X A m o d q Y_Aa^{X_A}mod q YAaXAmodqBob计算 Y B a X B m o d q Y_Ba^{X_B}mod q YBaXBmodq二者互相发送消息再分别计算幂次并取余获得的就是密钥这是二者获得的密钥相同这是因为 ( a x m o d p ) y m o d p a x y m o d p (a^x mod p)^ymod pa^{xy}mod p (axmodp)ymodpaxymodp。
此时就算信道中有监听者获得了 Y A Y B Y_AY_B YAYB但因为离散对数难题他也无法获知私钥从而也无法获得最终的密钥K。
RSA
这应该是名气最大的一种加密算法了几乎被人研究透了当作学习范本再来研究一下吧。
一般流程为 1选择大素数pq 2np*q 3n的欧拉函数 ψ ( n ) ( p − 1 ) ∗ ( n − 1 ) \psi(n)(p-1)*(n-1) ψ(n)(p−1)∗(n−1) 4存在于 ψ ( n ) \psi(n) ψ(n)互素的整数e 1 e ψ ( n ) 1e\psi(n) 1eψ(n) 5计算出e对 ψ ( n ) \psi(n) ψ(n)的模反元素d 6公钥en 7私钥dn 明文M加密 M e m o d n C M^emod nC MemodnC密文C解密 C d m o d n M C^dmod nM CdmodnM
该算法的安全性建立在离散对数难题的基础上即 x a y m o d p xa^y mod p xaymodp当p很大时很难求出y。
数学原理一个个解释首先是欧拉函数及计算 欧拉函数指小于n的正整数中与n互素的数的个数如果n为素数 ψ ( n ) n − 1 \psi(n)n-1 ψ(n)n−1n如果能分解为两个素数之积即$\psi(n)\psi(pq)\psi§\psi(q)(p-1)*(q-1)$1
模反元素指当e与 ψ ( n ) \psi(n) ψ(n)互素一定有一个整数d使 e d − 1 被 ψ ( n ) ed-1被\psi(n) ed−1被ψ(n)整除d为e的模反元素即 e d − 1 k ψ ( n ) ed-1k\psi(n) ed−1kψ(n)。
证明私钥能解密 C d m o d n ( M e m o d n ) d m o d n M e d m o d n m o d n M k ψ ( n ) M m o d n C^d mod n(M^e mod n)^d mod nM^{ed}mod n mod nM^{k\psi(n)}M mod n Cdmodn(Memodn)dmodnMedmodnmodnMkψ(n)Mmodn 因为n是很大的数如果 M k ψ ( n ) 1 M^{k\psi(n)}1 Mkψ(n)1上式取余的结果就是M该步骤可由费马小定理证明且涉及一些数论的知识详细可见RSA中的数论基础笔者作为了解选择只记住结论。
ECC椭圆曲线
椭圆曲线指 y 2 x 3 a x b , 4 a 3 27 b 2 ! 0 y^2x^3axb,4a^327b^2!0 y2x3axb,4a327b2!0的方程。
椭圆曲线困难问题
该问题与离散对数和大数分解等问题不同椭圆曲线利用数形结合的思想建立困难问题数学形式表达为 Q k P QkP QkP其中P为基点Q为公钥k为私钥但 k P kP kP不是简单数乘运算而是在椭圆曲线上先建立直线再找对称点AB的示例图如下 连接AB取与椭圆曲线的交点再找关于x轴的对称点作为AB的结果 如果是AA时就是A点的切线与椭圆曲线的交点n个A求和时下一个落点并没有什么规律也就是已知A计算nA是简单的但已知nA求n是复杂的这是椭圆曲线密码安全性的基础部分落点展示如下图
椭圆曲线加解密过程
1选取椭圆曲线 E p ( a , b ) Ep(a,b) Ep(a,b)上的一个点作为基点 2选大数k作为私钥生成公钥 Q k P QkP QkP 3选取随机数r密文C明文M加密 C ( r P M r Q ) C(rPMrQ) C(rPMrQ)密文是一个点对 4解密 M r Q − k ( r P ) M r ( k P ) − k ( r P ) M MrQ-k(rP)Mr(kP)-k(rP)M MrQ−k(rP)Mr(kP)−k(rP)M
后续还有复杂的数学理论知识感兴趣可以看椭圆曲线加密算法。
SM2
SM2是我国根据椭圆曲线制定的国家密码标准相关文件链接可见密码管理局具体包括数字签名协议密钥交换协议和公钥密码算法本文将介绍公钥密码算法。
SM2的私钥为 d B d_B dB公钥 p B [ d B ] G p_B[d_B]G pB[dB]Gklen为明文长度G为基点该方法正向易求反向难求 d B d_B dB加密过程如下 1密文 C C 1 ∣ ∣ C 3 ∣ ∣ C 2 CC_1||C_3||C_2 CC1∣∣C3∣∣C2即三部分的拼接明文M下面将分别计算 C i C_i Ci 2 C 1 [ k ] G C_1[k]G C1[k]G 3 C 3 H a s h ( x ∣ ∣ M ∣ ∣ y ) , ( x , y ) [ k ] p B C_3Hash(x||M||y),(x,y)[k]p_B C3Hash(x∣∣M∣∣y),(x,y)[k]pB拼接一段hash值 4 C 2 M ⊕ t t K D F ( x ∣ ∣ y ∣ ∣ k l e n ) C_2M⊕ttKDF(x||y||klen) C2M⊕ttKDF(x∣∣y∣∣klen)KDF为密钥派生函数用于共享秘密比特串中派生出密钥数据该函数又需要使用密码杂凑算法 H 2 H_2 H2具体见下图文件 详细方法都在官方文档中有兴趣可进一步研究。
哈希函数—SHA1
英文为hash音译为哈希也称作散列函数目的是将不等长的数据转化为等长输出详细原理可见常见的hash算法及原理。简单来说就是将数据通过哈希函数映射到类似数组结构的哈希表上因为数据多可能产生同样的序号如何处理冲突的哈希值是哈希函数的关键。
通常的哈希是不需要密钥的只根据消息计算摘要而几乎不可能逆向推出原消息可用于验证完整性该方法还可用于签名等安全机制消息或文件先进行哈希计算摘要再使用私钥加密哈希值接收者公钥解密重新计算哈希值并比较一致则说明未被修改过。
MD5易产生碰撞产生了SHA1但其安全性还不够有了更安全但也更慢的SHA2随着量子计算机的发展SHA3甚至说可以应对量子计算机的威胁这都太前端了民用领域SHA1应该就很足够用了所以笔者稍微学习了一下该算法。
SHA1中文名安全散列算法输入一个0到 2 64 2^{64} 264位的消息固定输出160bit的消息摘要。
首先将明文进行补位SHA1运算基于长度为512的明文分组所以需要先将明文M补至512的整数倍就算消息已经是512的倍数也需要补直到满足 L m o d 512 448 Lmod 512448 Lmod512448余64位用于存消息长度。 具体补的形式是最后一位加1其余位补足够的0。计算时使用多个512分组散列生成160bit摘要并参与下一次运算直到最后类似链式计算结构如下图 具体运算需要4轮×20个步骤产生160bit结果存于5个32位的连接变量中a、b、c、d、e。详细步骤如下
1512位的块分为16×32的向量 M [ 0 ] . . . M [ 15 ] M[0]...M[15] M[0]...M[15]扩充到80×32的 W [ 0 ] . . . W [ 79 ] W[0]...W[79] W[0]...W[79]。具体扩充方法为 W t M t , 0 t ≤ 15 W_tM_t,0t \le15 WtMt,0t≤15 W t R O T L 1 ( W t − 3 ⊕ W t − 8 ⊕ W t − 14 ⊕ W t − 16 ) , 16 ≤ t ≤ 79 W_tROTL^1(W_{t-3}⊕W_{t-8}⊕W_{t-14}⊕W_{t-16}),16\le t\le79 WtROTL1(Wt−3⊕Wt−8⊕Wt−14⊕Wt−16),16≤t≤79即异或后左移一位。
280轮运算
for t0 to 79{Ta左移f(b,c,d)ktwteddccb左移30位baaT}其中kt是常量对应t不同取值不同ft为分段函数运算。最终 H i a / b / c . . H i H_ia/b/c..H_i Hia/b/c..Hi实现更新迭代。
总结
本章学习了密码学的两大分类对称密码和非对称密码对称密码现在就用AES非对称最安全的是椭圆曲线详细实现过程这换那换的其实很麻烦非数学专业很难理解也记不住学习算法特性和应用场景即可。
对称密码基本能实现信息的保护但因为密钥作为信息也要在网络中传递为了保证密钥的安全需要使用非对称密码此外非对称密码还可以实现数字签名鉴权过程。不同于加密过程散列将不等长消息输出等长摘要可用于验证完整性。
虽然说是第二次学但这次零零散散也算折腾八小时很多算法的具体步骤和原理并没有搞清楚涉及到较为深入的数论知识实在让人头大。作为一般的程序开发者甚至安全人员的从业者了解到这也基本够了。
