【总结】密码学详细学习_风舞雪凌月的博客-程序员秘密

技术标签: 算法  总结  安全  linux  密码学  云计算  

备注

2021/12/3 星期五
多门考试和课程设计接踵而至,我只能选择用两天时间突击密码学了,边学边记录一下

一、基本知识

1.术语

  • 明文:没有经过加密,任何人都能看得懂的文字
  • 密文:经过加密后的文字
  • 密钥:明文与密文转换的参数

2.保密原则

是现代密码学和古典密码学的重要区别

  • 现代密码原则:密码系统的安全性不依赖于算法的保密而依赖于密钥的安全
  • 古典密码原则:密码系统的安全性依赖于算法的保密和密钥的安全

3.安全性

绝对安全(无条件安全):
指的是攻击者在拥有无限的计算资源的条件下也无法被攻破的秘密体制,对于一个加密算法,如果明文空间的每种概率分布,其中的每个明文和每个密文都满足,不论特定密文是否出现,特定明文出现概率都相同(即:P(M=m|C=c) = P(M=m))
计算安全:
攻击在有限计算资源的条件下很难攻破密码体制,将攻击者的攻击视作一个算法,要求算法的时间复杂度O(n^c)足够大,无法遍历密钥(n为密钥的二进制位数,c为常数)

当前默认加密算法至少需要能够抵抗选择明文攻击

4.安全目标

破坏性从上到下依次降低

  • 攻击者不能获得密钥
  • 攻击者不能获得全部明文
  • 攻击者不能获得明文的任何部分
  • 攻击者不能获得明文的任何函数

5.加密原则

  • 扩散(diffusion):明文及密钥的影响尽可能散布到多密文中(置换)
  • 混淆(confusion):使明文和密文间的统计相关性最小化(代换)

6.数学基础

包括数论、概率论、近世代数、代数几何、计算复杂性

7.数学难题

多项式求解、离散对数、大整数分解、背包问题、二次剩余、模n平方根、Diffie-Hellman

二、密码编码

1.古典密码

(1)置换密码

明文中的字符保持不变,通过改变字符顺序进行加密

  • 栅栏密码:
    加密:将明文分成k组,取每组的第i个字符连成密文段i,再将密文段全部相连形成密文
    解密:将密文分成k组,取每组的第i个字符连成明文段i,再将明文段全部相连形成明文
    密钥:k

(2)代换密码

明文中的字符顺序保持不变,通过将字符替换成其他字符进行加密

单字符代换:

单表代换:

  • 加法密码:
    (也叫移位密码特例为凯撒密码)
    加密:E(x)=(x+k)%m
    解密:D(x)=(x-k)%m
    密钥:k
  • 乘法密码:
    加密:E(x)=(kx)%m
    解密:D(x)=(k^-1
    x)%m
    密钥:k
  • 仿射密码:
    加密:E(x)=(a*x+b)%m
    解密:D(x)=(x-b)/a%m
    密钥:(a,b)
  • 棋盘密码:
    编制密码表:绘制5*5的方格,将i和j放入同一个格子,给每一个格子一个坐标(x,y)
    加密:将明文依次替换为坐标对
    解密:将密文在密码表中找到坐标对应的值

多表代换:

  • 维吉尼亚密码:
    加密:E(x)=(x[i]+k[i%n])%m
    解密:D(x)=(x[i]-k[i%n])%m
    密钥:k[n]

多字符代换

  • 普莱费尔密码:
    编制密码表:
    1.绘制5*5方格
    2.选取密钥(任意字符组合)
    3.将密钥依次填入方格(重复的字符只保留第一次出现的位置,字符I和L视作同一个字符)
    4.其余字符按顺序填入方格
    5.整理明文,每两个字符组成一对,两相同字符相连时在中间插入X
    加密:
    1.明文对在同一行时,密文为其右侧的字符
    2.明文对在同一列时,密文为其下方的字符
    3.明文对在不同行列时,密文为明文对所在正方形的另外两个角点上的字符
    解密:
    1.密文对在同一行时,明文为其右侧的字符
    2.密文对在同一列时,明文为其上方的字符
    3.密文对在不同行列时,明文为密文对所在正方形的另外两个角点上的字符

一次一密

每次加密都使用全新的密钥,每个密钥仅使用一次,是理论上绝对安全的加密方式

  • 费纳姆密码:

2.现代密码

(1)对称密码(单钥密码)

优点:加密快,密钥短,历史悠久
缺点:密钥管理困难,不能进行身份认证和数字签名
序列密码(流密码):
给定种子通过算法生成密钥流,再将明文位或字符分别与密钥流进行模加法运算
基础:有限状态自动机,二元序列伪随机,线性反馈移位寄存器,m序列

  • A5-1:
    应用:蜂窝电话手机到基站间的通信加密,用户sim卡中有不发生改变的基本密钥K1,在产生会话时基站生成64位随机密钥k,并使用k1加密,发送给用户,用户使用k1解密后得到随机密钥k,随机密钥仅一次通话内有效。
  • RC4:
    算法:
    1.初始置换
    (1)线性填充256位长的s表s[i]=i
    (2)循环使用种子填充256位长的k表k[i]=seed[i%n]
    (3)用k表对s表进行初始置换,j=(j+s[i]+k[i])%256(j初始为0),交换s[i]和s[j]的位置
    2.密钥流生成
    (1)i,j初始为零
    (2)循环加密每一位,i=(i+1)%256,j=(j+s[j])%256,交换s[i]和s[j],t=(s[i]+s[j])%256
    (3)s[t]就是这一位的位密钥,与该位进行异或得到位密文

(2)分组密码(块密码)

将明文划分为若干组(一般64位一组),再将各分组加密
基础:SP网络,Feistel结构、SPN结构

  • DES:
    衍生:3DES
    算法:
    1.输入64位的明文数据
    2.初始置换IP
    3.在轮函数F中进行16轮迭代变换
    4.逆置换IP^-1
    5.得到64位密文数据
    轮函数:
    先将64位数据分成左右两部分(L,R),每轮计算时,记录R成为下一轮的L,同时让R经过扩展表(E盒)、代换表(S盒)、置换表(P盒)的变换再与L进行异或成为下一轮的R
    密钥生成算法:
    1.初始置换(PC-1):根据置换表去除校验位并对剩余字符进行置换
    2.轮迭代:将初始置换得到的56位字符分左右两部分(C,D),C,D分别向左循环移动移位得到下一轮的(C,D),并将本轮(C,D)输入置换表PC-2得到本轮的密钥K(48位)

  • AES:
    衍生:AES-128、AES-192、AES-256
    算法:
    1.白化(轮密钥加)
    2.进行轮迭代(128迭代10轮、192迭代12轮、256迭代14轮)[字节代换、行移位、列混淆、轮密钥加]
    3.最后一轮迭代[字节代换、行移位、轮密钥加]
    设计原理:
    AES将一个字节视作一个系数为各位的七次多项式,而它可以通过在二元域上模一个不可约的八次多项式m(x)得到,选取m(x)为下x8 +x4 + x3+x+1并定义加法为两字节逐位异或,乘法为多项式在模m(x)下相乘的结果。同理,也可以将一个字视作一个系数为各位的三次多项式,m(x)为x4+1。

  • SM4:
    国密算法

(2)非对称密码(双钥密码)

优点:密钥管理简单,能够进行身份认证和数字签名
缺点:运算慢,密钥长,发展较短

  • RSA:
    算法:
    1.密钥生成
    取不相等的两大素数p,q,令N=p*q,N的lambda函数为lcm(p-1,q-1),在1到lambdaN之间任取一与lambdaN互素的整数e,再求e在模lambda N下的逆元d,(e,N)为公钥(d,N)为私钥
    2.加密算法
    密文c=E(m)=m^e(modN)
    3.解密算法
    明文m=D=c^d(modN)
    另:计算ab(modN)的方法是二元法,先将b写成二进制形式,然后分离每一位(最高位为1号其他位依次编号)。令c[0]=1,c[i]=c[i-1]2*m(b[i]-1)
  • ElGamal:
    算法:
    1.密钥生成
    取一大素数p,求其生成元g,找一随机数做私钥x,通过g^x%p求公钥y
    2.加密算法
    密文有两部分,先选一个随机数k,求出c1=gk%p,c2=m*yk%p,密文为(c1,c2)
    3.解密算法
    直接计算m=c2*(c1x)-1即为明文
    另:该算法是不确定性的,同一个密文使用不同的随机数k加密得到的密文不同(同一个密文最多有p-1个明文),所以k必须保密且仅使用一次,如果使用相同k被攻击者得到,则可通过y^k%p得到私钥
  • ECC:
    算法:

(3)单向函数

也叫散列函数、杂凑函数或哈希函数,将任意长度的信息映射为较短的、固定长度的值,一般用于消息摘要

  • MD5:
  • SHA:
    衍生:SHA-1、SHA-128、SHA-256

三、数字签名与密钥管理

1.数字签名

  • RSA:
  • 签名算法:
    与加密算法一致,但是使用私钥进行加密
    验证算法:
    与解密算法一致,但是使用公钥进行解密
  • ElGamal:
    签名算法:
    1.任选一个与大素数p的欧拉函数f互素的整数k
    2.计算s1=gkmodp,s2=(m-x*s1)*k-1modf
    3.(s1,s2)为签名
    验证算法:
    签名真实的等价条件为ys1*s1s2=gm(mod p)

2.密钥管理

(1)密钥生成

(2)密钥分发

密钥协商(Diffie-Hellman):

中心分发(KDC):

四、密码分析

1.敌手模型

敌手一般假定在发送方与接收方之间,能够截获密文并企图恢复明文

2.攻击场景

攻击性从上到下依次提高

唯密文攻击: 攻击者只能得到若干条同一密钥加密的密文
已知明文攻击: 攻击者能拿到若干同一密钥加密的明密文对
选择明文攻击: 攻击者可以选择一些明文并得到对应的密文
选择密文攻击: 攻击者可以选择一些密文并得到对应的明文

3.攻击方式

(1)穷举法

暴力穷举: 穷举全部密钥
字典攻击: 用所有可能的密钥组成一个字典进行穷举

(2)频率分析

利用明文已知的统计规律进行破译
单字符:
最常出现依次为E、T、A、O、I、N、S、H、R、D、L(有效攻击单字符替换和置换密码)
双字符:
最常出现依次为TH、HE、IN、ER、AN、RE、DE、ON、ES、ST、EN、AT、TO、NT、HA、ND(有效攻击多字符替换和置换密码)
三字符:
最常出现依次为THE、ING、AND、HER、ERE、ENT、THA、NTH、WAS、ETH、FOR、DTH(有效攻击多字符替换和置换密码)

(3)长度测试法

两个相同的明文段加密成相同的密文段,则者两个明文段之间的距离大概率是密钥长度的整数倍。当有多个相同段时,密钥长度大概率为段间距的最大公因数的因数。再利用重合指数法就可以验证密钥长度

(4)重合指数法

当猜对密钥时,计算的概率值约为0.065,否则约为0.038

(5)社会工程学

通过对知道算法的人的渗透获得算法

(6)逆向工程学

对含有加密算法的程序进行逆向工程获取其算法

(7)彩虹表攻击

预先计算常见的加密值形成数据库,破解时查表得到明文

(8)确定性分析

利用已知两和数学关系进行破译

(9)差分密码分析

通过分析两个明文差值对密文的影响推断密钥,利用拉格朗日公式的思想,推断加密算法的等价变换破译密码

(10)线性密码分析

寻找给定密码的算法的近似表达破译密码

(11)差分线性分析

将差分密码分析和线性密码分析组合破译

(12)密钥相攻击

根据有某种关系的明密文对进行分析攻击

导图

导图

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/l1447320229/article/details/121686498

智能推荐

为什么 switch 语句执行效率比 if-else 语句高?_执笔苦行僧的博客-程序员秘密_switch和ifelse哪个高效

在我们学习流程控制语句时不难发现,很多情况下能使用 if-else 语句的地方我们都能够使用 switch 语句来代替。有经验的开发者会建议我们,尽量使用 switch 语句来代替繁琐的 if-else。这样做的原因:switch 语句的执行效率会比 if-else 语句高。下面我们就写一个简单的程序来对其进行验证:public class Demo { public static void main(String[] args) { String aaa = "aaa".

【比特币】Ubuntu 16.04 编译比特币源码 报错解决_YuXi_0520的博客-程序员秘密

Ubuntu 16.04.我是装在了虚拟机上,相关配置请参考前面博客VirtualBox安装ubuntu16.04及其配置【虚拟机】VirtualBox ubuntu 源替换【虚拟机】VirtualBox ubuntu 配置虚拟机增强功能 双向拖拽一、安装第三方1、设置DNS域名解释器sudo vi /etc/resolv.conf然后把 nameserver 这修改如下name...

(简单dp)hdu1466 计算直线的交点数_是Elie呀的博客-程序员秘密

题目链接:(简单dp)hdu1466 计算直线的交点数Problem Description平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。Input输入数据包含多个测试实例,每个测试实例占一行,每行包含一个正整数n(n<=20),n表示直线的数量.Output每个测试实例对应一行输出,...

LeetCode881_救生艇_高压锅_1220的博客-程序员秘密

1. 题目第 i 个人的体重为 people[i],每艘船可以承载的最大重量为 limit。每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit。返回载到每一个人所需的最小船数。(保证每个人都能被船载)。示例 1:输入:people = [1,2], limit = 3输出:1解释:1 艘船载 (1, 2)示例 2:输入:people = [3,2,2,1], limit = 3输出:3解释:3 艘船分别载 (1, 2), (2) 和 (3)示例 3:输入:p

FBRetainCycleDetector iOS15 fishhook crash replace indirect_symbol_bindings[i] 的解决方法_冯子一的博客-程序员秘密

pod 'MLeaksFinder', :configurations => ['Debug'] post_install do |installer| ## Fix for XCode 12.5 find_and_replace("Pods/FBRetainCycleDetector/FBRetainCycleDetector/Layout/Classes/FBClassStrongLayout.mm", "layoutCache[currentClass

随便推点

使用OCCI连接Linux下Oracle数据库_weixin_34399060的博客-程序员秘密

 OCCI(OracleC++ Call Interface):C++程序与Oracle数据库实现交互的应用程序接口,它以动态连接库的形式提供给用户。OCCI对OCI实行了对象级的封装,其底层仍是OCI  OCCI连接Linux下的Oracle数据库:  1 安装Linux下的oracle客户端  2 下载对应的oracle-instantcl...

Ubuntu+Apache+PHP+Mysql环境搭建(完整版)(转)_dengping5156的博客-程序员秘密

http://www.2cto.com/os/201505/401588.htmlUbuntu+Apache+PHP+Mysql环境搭建(完整版)一、操作系统Ubuntu 14.04 64位,阿里云服务器二、Apache1、安装Apache,安装命令:sudo apt-get install apache22、环境配置:1)配置文件:路径为/etc/apac...

[ 移植 ] ___ Library : Mad____川流不息的博客-程序员秘密

MAD(libmad)是一种高质量的MPEG音频解码器。

spring boot 原理和代码分析_岚殿的博客-程序员秘密_springboot代码

spring 能干什么​ 来spring官网看看,我发现我所学习的只是它的冰山一角。微服务​ 支持模块化开发,把应用拆分成一个一个模块,好处其实有很多,我列举一些我自己能想到吧。​ 首先是解耦合,不至于每个模块的耦合很大,而且很方便程序员去设计数据库,因为需要考虑的东西确实是少了。​ 单从解耦合这个角度来看,我的各个模块可以独立部署,互不干扰,我测试或者更新其中一部分,对其他功能是没有任何影响的,这是单体应用无论如何都不可能做到的。​ 这个不得不说DDD,我觉得它里面有一个很好的思想,就是领

[python] PyMouse、PyKeyboard用python操作鼠标和键盘_weixin_34014277的博客-程序员秘密

 1、PyUserInput 简介PyUserInput是一个使用python的跨平台的操作鼠标和键盘的模块,非常方便使用。支持的平台及依赖如下:Linux - XlibMac - Quartz, AppKitWindows - pywin32, pyHook支持python版本:我用的是3.6.7 2、安装直接源码安装,python3加持:git clone https:...

设置table表格后边框单线_liukai6的博客-程序员秘密_table边框设置成单线

当我们给表格加上css样式加上边框会出现非常难看的双层线.这个时候把下面的样式粘贴进去就可以了 <style type="text/css"> td{border:1px black solid;} table{border-collapse:collapse;} </style> 主要table{border-collapse:collapse;}这就是关键

推荐文章

热门文章

相关标签