RSA算法
RSA算法简介
RSA密码算法是美国麻省理工学院的Rivest、Shamir和Adleman三位学者于1978年提出的。RSA密码算法方案是唯一被广泛接受并实现的通用公开密码算法，目前已经成为公钥密码的国际标准。它是第一个既能用于数据如密，也能通用数字签名的公开密钥密码算法。在Internet中，电子邮件收、发的加密和数字签名软件PGP就采用了RSA密码算法。
RSA的理论基础
RSA的理论基础是大整数因数分解的困难性质。
RSA加解密过程
密钥生成
选取两个大素数p,qp,qp,q
计算n=p⋅qn=p \cdot qn=p⋅q
计算欧拉函数 ϕ(n)=(p−1)⋅(q−1)\phi (n) = (p-1)\cdot(q-1)ϕ(n)=(p−1)⋅(q−1)
随机选取一个整数e(1<e<ϕ(n))e(1 < e < \phi(n))e(1<e<ϕ(n))，使满足gcd(e,ϕ(n))=1gcd(e,\phi(n))=1gcd(e,ϕ(n))=1
由扩展欧几里得算法计算d使得e⋅d mod ϕ(n)=1e \cdot d \space mo ...
积分推导中的双曲函数与三角函数的联系
积分公式引发的思考
从积分公式中我们会发现以下有意思的情景
∫11−x2dx=arcsinx+C1=−arccosx+C2\int \frac 1 {\sqrt{1-x^2}} dx = arcsinx+C_1= -arccosx+C_2
∫1−x21dx=arcsinx+C1=−arccosx+C2
∫1x2+1dx=arcsinhx+C\int \frac 1 {\sqrt{x^2+1}} dx = arcsinhx+C
∫x2+11dx=arcsinhx+C
∫1x2−1dx=x∣x∣arccosh∣x∣+C\int \frac 1 {\sqrt{x^2-1}} dx = \frac x {|x|} arccosh|x|+C
∫x2−11dx=∣x∣xarccosh∣x∣+C
∫11+x2dx=arctanx+C\int \frac 1 {1+x^2} dx = arctanx+C
∫1+x21dx=arctanx+C
∫1x2−1dx=x∣x∣arctanhx+C\int \frac 1 {x^2-1} dx = \frac x {|x|} arctanh ...
积分公式数形结合辅助记忆
以下公式仅用于辅助记忆，不可用于证明题，求积分公式本身的题目。
公式1
∫a2−x2dx=x2a2−x2+a22arcsinxa+C\int \sqrt{a^{2}-x^{2}} d x = \frac x 2 \sqrt{a^2-x^2} + \frac{a^2}2 arcsin \frac x a + C
∫a2−x2dx=2xa2−x2+2a2arcsinax+C
如图，函数y=a2−x2y=\sqrt{a^2-x^2}y=a2−x2 为上图的半圆，则原函数可表示为S=∫axa2−x2dxS=\int ^x _a \sqrt {a^2-x^2} dxS=∫axa2−x2dx,不妨设a=0a=0a=0,x=xCx=x_{C}x=xC，则SSS为如图阴影部分的面积。
阴影部分可拆分成两部分S1,S2S_1, S_2S1,S2，
三角形部分的S2S_2S2可表示如下
S2=12xCyC=x2a2−x2S_2 = \frac 1 2 x_C y_C=\frac x 2 \sqrt{a^2-x^2}
S2=21xCyC=2xa2−x2
扇形部分的S1 ...
S-DES加密过程
加密模型
输入输出
算法流程
密钥生成流程
已知10位的种子密钥k=(k0,k1,...,k9)k=(k_0,k_1,...,k_9)k=(k0,k1,...,k9)
执行P10P10P10置换变换得到m1=P10(k)m_1=P10(k)m1=P10(k)
5位一组分割成两组，每组内循环左移s位记作变换SLsSL_sSLs，对m1m_1m1进行5位一组分割的循环左移1位变换，得m2=SL1(m1)m_2=SL_1(m_1)m2=SL1(m1)
执行10位变8位的P8置换变换得到k1=P8(m2)k_1=P8(m_2)k1=P8(m2)
对m2m_2m2进行5位一组分割的循环左移2位变换，得m3=SL2(m2)m_3=SL_2(m_2)m3=SL2(m2)
执行10位变8位的P8置换变换得到k2=P8(m3)k_2=P8(m_3)k2=P8(m3)
加密流程
先来看加密算法，已知明文ppp
对ppp执行初始变换IPIPIP得到IP(p)IP(p)IP(p)
对IP(p)IP(p)IP(p)执行依赖密钥k1k ...
Hill密码
Hill密码
已知明文“Thank you”，密钥为
K=[1203]K=\begin{bmatrix}
1 & 2\\
0 & 3
\end{bmatrix}
K=[1023]
加密公式为C=KmC=KmC=Km ，试用Hill密码算法进行加密，并求出K−1K^{-1}K−1，用你得到的密文进行解密验算。
手算过程
加密过程
将消息划分为m1,m2,…,m8 = t,h,…,u
[c1c2]=K⋅[m1m2]=[1203]⋅[197]=[3321]mod 26=[721]=[hv]\begin{bmatrix}
c_1 \\
c_2
\end{bmatrix}
=
K
\cdot
\begin{bmatrix}
m_1 \\
m_2
\end{bmatrix}
=
\begin{bmatrix}
1 & 2\\
0 & 3
\end{bmatrix}
\cdot
\begin{bmatrix}
19 \\
7
\end{bmatrix}
=
\begin{bmatrix}
33 \\
21
\end{bmatrix}
mod \ ...
Vigenere密码
Vigenere密码
设明文为“visit beijing tomorrow”,密钥为“enjoy”,试用Vigenere算法进行加密。
手动实现
a
b
c
d
e
f
g
h
i
j
0
1
2
3
4
5
6
7
8
9
k
l
m
n
o
p
q
r
s
t
10
11
12
13
14
15
16
17
18
19
u
v
w
x
y
z
20
21
22
23
24
25
c1 = (v+e) % 26 = (21+4) % 26 = 25 = z
c2 = (i+n) % 26 = (8+13) % 26 = 21 = v
同理c = zvbwr onwhmap rszxfpsj
代码实现
1234567891011121314151617181920212223242526272829303132333435#include <iostream>using namespace std;char getTableElement(char a, char b) { a -= & ...
Playfair密码
Playfair密码
Playfair密码出现于1854年，它将明文中的双字母组合作为一个单元对待，并将这些单元转换为密文双字母组合。Playfair密码基于一个字母矩阵，该矩阵使用一个关键词（密钥）来构造。
字母矩阵
其构造方法是：从左至右、从上至下依次填入关键词的字母（去除重复的字母），然后再以字母表顺序依次填入其他字母。字母I和J被算为一个字母（即J被当做I处理）。
如密钥为monarchy，则构造字母矩阵如下：
当密钥串有重复字符出现时，需要去重，否则矩阵将无法覆盖26个字母。
我们可以方便地实现字母矩阵的数据结构的代码如下，
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include <iostream>#include <sstream>#include ...
密码学基本术语
基本术语
（1）明文（Plaintext/Message）：指待加密的信息，用P或M表示。明文可以是文本文件、图形、数字化存储的语音流或数字化的视频图像的比特流等。
（2）密文（Cipertext）：指明文经过加密处理后的形式，用C表示。
（3）加密（Encryption）：指用某种方法伪装消息以隐藏它的内容的过程。
（4）加密算法（Encryption Algorithm）：指将明文变换为密文的变换函数，通常用E表示。
（5）解密（Decryption）：指把密文转换成明文的过程。
（6）解密算法（Decryption Algorithm）：指将密文变换为明文的变换函数，通常用D表示。
（7）密钥（Key）：变换函数所用的一个控制参数。加密和解密算法的操作通常是在一组密钥控制下进行的，分别称为加密密钥和解密密钥，通常用K表示。
（8）密码分析（Cryptanalysis）：指截获密文者试图通过分析截获的密文从而推断出原来的明文或密钥的过程。
（9）被动攻击（Passive Attack）：指对一个保密系统采取截获密文并对其进行分析和攻击。这种攻击对密文没有破坏作用。
（10）主动攻 ...
凯撒密码及其变种
凯撒密码
凯撒密码是把字母表中的每个字母用该字母后面第3个字母进行替代，如表3-2所示。为便于区分，我们用小写字母表示明文，大写字母表示密文。
明文：this is a book。
密文：WKLV LV D ERRN。
明文和密文空间是26个字母的循环，所以z后面的字母是a。如果为每个字母分配一个数值(a=0，b=l，…，z=25)，则该算法能够表示如下：
C=EK(p)=(p+3)%26C=E_K(p) = (p+3) \% 26
C=EK(p)=(p+3)%26
变种
我们可以把每个字母用该字母后面第k个字母进行替代，即
C=EK(p)=(p+k)%26C=E_K(p) = (p+k) \% 26
C=EK(p)=(p+k)%26
便得到凯撒密码的变种加密方式了。
代码实现
123456789101112131415161718192021222324// 凯撒密码的加密// key为加密字符相对原字符的向后偏移量string encrypt(string message, int key) { // 加密后的字符串长度应该和原字符串相同 stri ...
线段组求交算法的 SIMD 矢量化优化实践
问题定义
设线段 AAA 由顶点 (Asx,Asy)(A_{sx}, A_{sy})(Asx,Asy) 和顶点 (Aex,Aey)(A_{ex}, A_{ey})(Aex,Aey) 组成，记为 (Asx,Asy) (Aex,Aey)‾\overline{(A_{sx}, A_{sy})\;(A_{ex}, A_{ey})}(Asx,Asy)(Aex,Aey)。
设线段集 BBB 包含 nnn 条线段：
B={(Bsx[0],Bsy[0]) (Bex[0],Bey[0])‾,(Bsx[1],Bsy[1]) (Bex[1],Bey[1])‾,…,(Bsx[n−1],Bsy[n−1]) (Bex[n−1],Bey[n−1])‾}B = \left\{
\overline{(B_{sx}[0], B_{sy}[0])\;(B_{ex}[0], B_{ey}[0])},
\overline{(B_{sx}[1], B_{sy}[1])\;(B_{ex}[1], B_{ey}[1])},
\dots,
\overline{(B_{sx}[n-1], B_ ...