加解密

csuzhucong

已于 2022-02-16 00:41:08 修改

阅读量2.3k

点赞数

文章标签：算法

于 2021-04-12 16:24:50 首次发布

本文链接：https://blog.csdn.net/nameofcsdn/article/details/115627003

版权

（3）Pollard's rho 素数分解算法

1，DH算法（Diffie–Hellman）

5，完全正向保密（PFS，perfect forward secrecy）

四，OJ实战

力扣 91. 解码方法（组合计数）

力扣 535. TinyURL 的加密与解密

CSU 1059 Password

一，加密基础知识

1，加密函数、密钥、反函数

假设加密函数是f(x)=(ax+b)%255，其中x的范围是0-255，求出来的f(x)的范围自然也是0-255，算法是公开的，a，b就是密钥。
加密函数的反函数是 $g(x)=(x-b)*a^{-1}\%255$
f(x)拥有反函数 $\Leftrightarrow$ a和255互质。
例如a=2, b=3，函数f(x)=(2x+3)%255的反函数是g(x)=(x-3)*128%255

2，加密、解密

发送者把信息表示成字符串，每个字符的ASCII码是0-255，通过函数f(x)把每个字符转化成另外一个字符，然后把得到的字符串发送出去，同时还需要想办法把密钥发出去而不被拦截。
例如‘0’是48, f(48)=99，也就是‘c’
接受者根据密钥得到具体的解密函数，即可破解信息。

3，对称加密

这种加密和解密用同一份密钥的加密算法，叫对称加密。
对称加密的最大弊端就是，一旦密钥被拦截，加密算法就完全失效。
常见对称加密、解密、破解常见对称加密、解密、破解_nameofcsdn的博客-CSDN博客_对称解密

4，非对称加密、公钥私钥

如果可以构造一个函数f和反函数g，使得通过f推导g是几乎无法实现的，那么我们就可以公开f，保留g。
信息发送方式：接收方公开f，加密方用f加密并发送，接收方用g解密。因为不需要传输g，所以安全性大大的提高。

二，非对称加密

非对称加密体系都是建立在数学的基础之上的，目前一般分为三类：大素数分解问题类、离散对数问题类、椭圆曲线类

1，大素数分解问题类

（1）RSA

接收方A取 2 个大素数p,q, 令n=pq，当p和q足够大时，无法对n进行因式分解。（换句话说，以目前人类的数学能力和计算机能力找2个大素数是很简单的，但是分解素因子是很难的）
那么，接收方知道 $\varphi({n})$ 的值，但是其他人无法算出来。
取e,d 使 $\mathrm{ed} \equiv 1(mod \varphi({n}))$ ,将e, n 公开, 这就是公钥，d保留，这就是私钥。
发送方B将密文m变成 $\mathrm{m}^{\mathrm{e}} \equiv \mathrm{c}(\mathrm{mod}\ n)$ 发送给A，
A计算 $\mathrm{c}^{\mathrm{d}} \equiv \mathrm{m}(\mathrm{mod}\ \mathrm{n})$ 得到原文m
RSA是应用非常广泛的非对称加密算法，所有的windows和ATM机用的都是RSA算法，RSA的一个比较知名的应用是SSL

（2）Rabin

另外一种类似的非对称加密是Rabin
A取 2 个大素数 p,q, 令n=pq, 将 n 公开,
B将密文 m 变成 $\mathrm{m}^{2} \equiv \mathrm{c}(\mathrm{mod} \ n)$ 发送给 A， A求解 $\mathrm{x}^{2} \equiv \mathrm{c}(\bmod \mathrm{p})$ 和 $\mathrm{x}^{2} \equiv \mathrm{c}(\mathrm{mod}\, q)$ ，再求m

（3）Pollard's rho 素数分解算法

这个是因数分解的算法，时间复杂度为 $O(n^\frac{1}{4}logn)$

Pollard‘s rho大数分解算法_nameofcsdn的博客-CSDN博客

2，离散对数问题类

在有限域 $F_p$ 中取1个数a，再取b=a^x，那么根据b和a求x就是一个很困难的问题，x就是离散对数。

为了让破解最难，a一般取原根

3，椭圆曲线类

利用椭圆曲线上的加法运算，设计出不可求反的函数。

椭圆曲线加密椭圆曲线加密_nameofcsdn的博客-CSDN博客

4，广义离散对数问题的求解

离散对数求解、BSGS算法离散对数求解、BSGS算法_nameofcsdn的博客-CSDN博客

三，对称密钥交换

对称加密需要交换密钥，目标是通讯双方知道同一个密钥，其他任何用户都不知道。

这就涉及到密钥如何传递的问题，就像传统加密，需要用一个密码本（实体本子），已最高安全级别传递，而后根据密码本上的密钥加密。

1，DH算法（Diffie–Hellman）

（1）算法原理

首先Alice与Bob共享一个素数 p 以及该素数 p 的原根 g，

而后Alice产生一个私有的随机数 A，计算 g^A=Ya (mod p)，将结果 Ya 通过公网发送给Bob

同样的，Bob保留随机数B，发送Yb给Alice

所以，双方共享的信息是p,g,Ya,Yb四个数，这都是可以被直接拦截的，双方私有的分别是A和B，这是安全的。

最后，Alice计算Yb^A，Bob计算Ya^B，这2个数是相同的，而且是安全的。

（2）破解方法——中间人攻击

如果攻击者能截断通讯，那么他就能分别和Alice、Bob加密通讯，DH算法是无法识别对方身份的，需要别的认证算法才能完成。

所以，密码学里面经常提到的算法有三类：加密、密钥交换、认证。

2，DHE、EDH

DHE应该是Diffie–Hellman key exchange，DHE就是DH

EDH应该是Ephemeral Diffie–Hellman，即短暂DH

A cryptographic key is called ephemeral if it is generated for each execution of a key establishment process.

3，ECDHE

DHE是建立在狭义离散对数问题的基础之上的，如果换成椭圆曲线，那就是ECDHE

4，用RSA做对称密钥交换

A想和B进行密钥交换，获得一个新的密钥，于是A就通过B的公钥加密了一个密钥K，然后将生成的密文发给B。B接到了这个密文之后使用自己的私钥解密获得密钥K。

用RSA做对称密钥交换，同样可以中间人攻击。

一般的，如果用RSA做对称密钥交换，认证算法也会选择RSA

5，完全正向保密（PFS，perfect forward secrecy）

完全正向保密指的是一个密钥被破解，并不影响其他密钥的安全性。设计旨在长期使用密钥不能确保起安全性的情况下而不影响过去会话的保密性。

DHE和ECDHE有PFS特性，而RSA没有PFS特性，所以一般选择ECDHE>DHE>RSA

四，OJ实战

力扣 91. 解码方法（组合计数）

一条包含字母 A-Z 的消息通过以下映射进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26
要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"111" 可以将 "1" 中的每个 "1" 映射为 "A" ，从而得到 "AAA" ，或者可以将 "11" 和 "1"（分别为 "K" 和 "A" ）映射为 "KA" 。注意，"06" 不能映射为 "F" ，因为 "6" 和 "06" 不同。

给你一个只含数字的非空字符串 num ，请计算并返回解码方法的总数。

题目数据保证答案肯定是一个 32 位的整数。

示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2：

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
示例 3：

输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
示例 4：

输入：s = "06"
输出：0
解释："06" 不能映射到 "F" ，因为字符串开头的 0 无法指向一个有效的字符。

提示：

1 <= s.length <= 100
s 只包含数字，并且可能包含前导零。

我的分析：

这题的输入是任何纯数字的字符串都有可能，要判断是否合法就只需要看字符0的前面是不是1或者2

我的思路是直接根据0进行截断，每一段中进行分析，最后化成斐波那契数列。

int F[] = { 1 ,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,
46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,
24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903 };

class Solution {
public:
    int numDecodingsNoZero(string s) {
        int ans = 1, start = -1;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] <= '2')continue;
            if(s[i] > '6' && start<i-1 && s[i-1]=='2')ans *= F[i - start-1], start = i;
            else ans *= F[i - start], start = i;
        }
        return ans*F[s.length()-1-start];
    }
    int numDecodings(string s) {
        for (int i = 0; i < s.length(); i++)if (s[i] == '0') {
            if (i == 0 || s[i - 1] > '2')return 0;
            string s1 = s.substr(0, i - 1), s2 = s.substr(i + 1, s.length() - i - 1);
            return numDecodingsNoZero(s1) * numDecodings(s2);
        }
        return numDecodingsNoZero(s);
    }
};

力扣 535. TinyURL 的加密与解密

TinyURL是一种URL简化服务，比如：当你输入一个URL https://leetcode.com/problems/design-tinyurl 时，它将返回一个简化的URL http://tinyurl.com/4e9iAk.

要求：设计一个 TinyURL 的加密 encode 和解密 decode 的方法。你的加密和解密算法如何设计和运作是没有限制的，你只需要保证一个URL可以被加密成一个TinyURL，并且这个TinyURL可以用解密方法恢复成原本的URL。

惊人的加解密：

class Solution {
public:
    string encode(string s) {
        return s;
    }
    string decode(string s) {
        return s;
    }
};

诡异的加解密：

class Solution {
public:
    unordered_map<string, string>m;
    string s;
    
    string encode(string longUrl) {
        string ans=s;
        s = m[s] = longUrl;
        return ans;
    }
    string decode(string shortUrl) {
        return m[shortUrl];
    }
};

CSU 1059 Password

题目：

Description

发送电报保密是一项重要的工作，尤其是在军事领域，所以，为了安全的需要常常会对发送的内容进行加密，然后，接收方再进行解密，这样就达到了安全的需要。

本次我们完成一个简单的对字母加密程序。首先对字母进行编号，小写字母a至z编号为1至26，大写字母A至Z分别编号27至52，这样每个字母都有唯一的一个序号，在发送内容时，我们以函数F(X)=X*X+X+1对发送字母的序号进行计算，就会获取个新的序号，对该序号再进行对52取余，该序号即为加密后的要发送字母的序号，这样就能达到加密的作用。

Input

有多组测试数据,每组测试数据占一行,包括需要加密的消息,消息的长度不超过100个字符,这些字符只包含大小写字母。

Output

输出加密后的字符,每个测试样例占一行。

Sample Input

abA

Sample Output

cgC

代码：

#include<iostream>
#include<string.h>
using namespace std;
 
int main()
{
	char c[101], ca = 'A';
	while (cin >> c)
	{
		for (int i = 0; i < strlen(c); i++)
		{
			int d = c[i] - ca + 1;
			if (d > 26)d -= 32;
			else d += 26;
			d = ((d*d) + d + 1) % 52;
			if (d > 26)d -= 26;
			else d += 32;
			cout << char(ca + d - 1);
		}
		cout << endl;
	}
	return 0;
}