RSA加密原理

• 感觉自己写的RSA密码分析还是比较杂，而且还有很多没有补充完整的，思来想去还是把从头开始把每个东西都完善一下。我之前打算的分类是每个RSA攻击方式，在正常RSA加密、多幂RSA加密、多素数RSA加密、对偶RSA加密、共素数RSA加密等都分析一遍。
• 但是这样的分类还是有点乱，最终决定依然按照《Cryptanalysis of RSA and Its Variants (M. Jason Hinek)》这本书的分类来进行分类。（之后如果有时间，再根据我上面的想法分个类。）
• 这篇博客正式开始我的RSA加密的密码分析学的学习，之前一直想写这个博客，但是由于基础知识有限以及时间关系一直就鸽了，现在基础知识跟上来了，直接开始疯狂学习。
• 之前也做过不少RSA加密的题型，所以我根据集合的划分，将RSA加密题型进行分类，尽我所能的将题型分类成如下图所示，我会根据我的分类进行学习。目前还没分类完成，只能说边学边分类吧（此图会不定期跟新与完善）。这个分类的构建有参考这本国外书籍：《Cryptanalysis of RSA and Its Variants (M. Jason Hinek)》

公钥密码学

• 公钥密码学这个概念在1970年~1980年之间流行起来的，这个概念是被Diffie、Hellman、Merkle这三个人提出的。如果想要了解公钥密码学的起源，可以参考Diffie所写的The first ten years of public-key cryptography。
• 基于Douglas R. Stinson（道格拉斯·R·斯廷森），对于密码系统的定义，我们在公钥密码学中使用下面的定义：
  • 公钥密码学五元组$(P,C,K,E,D)$
  • $P$是明文的有限集合
  • $C$是密文的有限集合
  • $K$是密钥的有限集合，被称为密钥空间。
  • $E$是加密映射的有限集合，所有的公钥加密算法都属于这个集合
  • $D$是解密映射的有限集合，所有的公钥解密算法都属于这个集合
  • 对于每一个密钥$k\in K$，有一个加密规则（其实也就是一个映射）$enc_K\in E$，并且对应着有一个正确的解密规则（也可以理解为一个映射）$dec_K \in D$。
    • 对于每一个加密映射$enc_K: P\rightarrow C$和解密映射$dec_K: C\rightarrow P$，这两个函数有$dec_K(enc_K(m))=m,m\in P$
    • 对于每一个密钥$k \in K$以及每一个明文$m \in P$，$enc_K(m)$和$dec_K(enc_K(m))$都非常容易计算。
    • 对于几乎所有$k \in K$来说，任何与$dec_K$等价且可有效计算的算法，都在计算上不能仅有$enc_K$（这是一个映射）推导得到。也就是说，在不知道$dec_K$的情况下，解密是困难的。
    • 加密规则$enc_K$是公开的而解密规则$dec_K$是非公开的。
• 其实换一种角度思考公钥密码系统，从另一种角度看，一个公钥密码系统包含了三个有效的可计算的算法：
  • 密钥生成算法：该算法定义了密钥空间$K$
  • 加密算法和解密算法：这两个算法共同定义了明文空间$P$和密文空间$C$

RSA加密原理

• RSA加密体制是第一个被公开发表的公钥密码体制。RSA密码提示最早由Gardner在1977年于《Scientific Amrican》上发表的一篇文章中介绍。其完整的研究论文则于次年1998年由发明者Rivest、Shamir和Adleman发表，这三位作者都隶属于麻省理工学院，该密码体制最初被称为MIT公钥密码体制。

• 接下来以非专业的术语大致讲解一下RSA加密和解密过程：

  • 定义：要加密的明文为$m$，加密后得到的密文为$c$
  • 前提准备1：先选取两个素数$p、q$，计算这两个素数的乘积$n=p*q$
  • 前提准备2：计算$n$的欧拉函数，$\phi(n)=(p-1)*(q-1)$
  • 公钥的生成：生成一个公钥$e$，要求$1<e<\phi(n)$，且$e$为整数，还需要满足$gcd(e,\phi(n))=1$（也就是两者互素）
  • 私钥的生成：确定私钥$d$，私钥需要满足$e*d\equiv1~mod~(~\phi(n)~)$
  • 加密算法如下：

  $$c = m^e~mod~(~n)$$

  • 解密算法如下：

  $$m = c^d~mod(~n)$$

  • 解密正确性验证：
    • 通过欧拉定理以及欧拉函数可以将原本计算量比较大的指数运算转换为求解逆元的运算。如果稍微了解一下求解逆元的过程，其实就知道求逆元的过程本质上就是解不定方程，还需要用上欧几里得算法。
    • 由$e*d\equiv1~mod(~\phi(n))$就可以得到：$e*d=1+k*\phi(n)$
    • 所以$c^d\equiv (m^{e})^{d}\equiv m^{ed}~mod(n)$
    • 通过代换就可以得到$c^d\equiv m^{ed}\equiv m^{k*\phi(n)+1}~mod(n)$
    • 通过欧拉定理有$a^{\phi(n)}\equiv 1~mod(~n),gcd(a,n)=1$
    • 最后得到$c^d \equiv m^{ed} \equiv m^{k*\phi(n)+1}\equiv m^{k*\phi(n)}*m\equiv m~mod(~n)$
  • $(n,e)$为公钥对，$(p,q,d)$为私钥对

• 接下来使用比较专业的术语再描述一下RSA公钥加密体制的具体算法：

  • 定义明文空间与密文空间：生成两个大素数$p、q$，让$N = pq$，$P=C=Z_N$（即明文空间和密文空间就是整数模N的集合，其实就是$[0,n-1]$这个范围内的整数集）

  • 定义密钥空间：$K = \{(N,p,q,e,d):ed\equiv 1~mod(~\phi(N))\}$，其中$\phi(N)=(p-1)(q-1)$是欧拉函数。

  • 定义加密、解密规则：

    • 对于每个密钥$k\in K,k=(N,p,q,e,d)$。
    • 有加密规则$enc_K:Z_N\rightarrow Z_N$，满足算法$enc_K(x)=x^{e}~mod(~N)$。
    • 有解密规则$dec_K:Z_N\rightarrow Z_N$，满足算法$dec_K(y)=y^d~mod(~N)$

  • 其中$x,y\in Z_N$，$(e,N)$这一对被称为RSA公钥，$(d,p,q)$这个三元组被称为RSA私钥。

  • 加密函数$enc_K(x)=x^e~mod(~N)$，其中$N$是不能在一定时间内分解出来，并且满足$gcd(e,\phi(N))=1$。这个加密函数就被叫做RSA function（RSA函数）或者RSA primitive（RSA基本式）

  • $N=pq$被叫做RSA modulus（RSA模数），两个素数$p、q$被叫做RSA primes（RSA素数）

  • $e$被叫做public exponent（公钥指数）或者encrypting exponent（加密指数）

  • d被叫做private exponent（私钥指数）或者decrypting exponent（解密指数）

  • 由于公私钥指数必须满足$ed\equiv 1~mod(~\phi(N)~)$，所以有$ed=1+k\phi(N)$其中k是小整数（相比p、q、n来说），而$ed=1+k\phi(N)$这个等式就被称为RSA key equation（RSA密钥等式，简称密钥等式）

  • 解密规则正确性：

    • 对于与$N$互素的元素$a$，由欧拉定理可以得到$a^{\phi(N)}\equiv 1~(mod~N)$
    • 给定公钥$(e,N)$，以及一个明文消息$m\in Z_N,gcd(m,N)=1$，计算得到密文$c=m^e~mod(~N)$
    • 使用解密规则，用上欧拉定理与密钥等式有：

    \begin{align} c^d~(mod~N) &\equiv (m^e)^d~mod(~N)\\ &\equiv m^{ed} ~mod(~N)\\ &\equiv m^{1+k\phi(N)} ~mod(~N)\\ &\equiv m*(m^{\phi(N)})^k~mod(~N)\\ &\equiv m ~mod(~N) \end{align}

    • 由于$m \in Z_N$，所以$c^d\equiv m~mod(~N)$可以直接用等号连接$c^d = m~mod(N)$

  • 除此之外$gcd(m,N)>1$这种情况应该尽量避免，因为在$gcd(m,N)>1$这一情况下使用RSA加密计算出密文$c$后，$c$一定会满足$gcd(c,N)=p$或者$gcd(c,N)=q$

RSA加密进一步理解

欧拉函数与卡迈尔函数

欧拉函数：

在数论中，对正整数n，欧拉函数$\phi(n)$是小于等于n的正整数中与n

互素的数的个数，又称为欧拉总计函数。其公式如下：

• $n$能被标准分解为$n=p_1^{k_1}p_2^{k_2}...p_r^{k_r}$
• $\phi(n)$有如下公式$\phi(n)=p_1^{k_1-1}p_2^{k_2-1}...p_r^{k_r-1}(p_1-1)(p_2-1)...(p_r-1)$

卡迈尔函数：

在数论中，正整数$n$的卡迈尔函数$\lambda(n)$定义为满足下列条件的最小正整数$m$，满足$a^{m}\equiv1~mod(~n)$，其中$a$为任意与$n$互素的整数。其递推公式如下：

$$\lambda(n)=\begin{cases} \phi(n),&n=1、2、4,或奇质数幂,\\ \frac{1}{2}\phi(n),&如果n=2^r,r≥3,\\ lcm(\lambda(n_1),\lambda(n_2),...,\lambda(n_k)),&如果n=n_1n_2...n_k,且n_1,n_2,...,n_k是不同质数的幂 \end{cases}$$

• RSA加密中，注意到有一个比较特别的地方，就是公钥指数$e$和私钥指数$d$在模$\phi(N)$下互为逆元，这个条件是能用解密规则将密文恢复成明文充分条件。而能解密出明文的必要条件是，公钥指数和私钥指数在模$N$的卡迈尔函数$\lambda(N)$下互为逆元。
• 因此，只需要在$\lambda(N)$的某个倍数下，使用公钥指数和私钥指数互为逆元即可。从这一点其实可以看出$\phi(N)$是$\lambda(N)$的倍数。这其实就允许我们在密钥生成算法中使用到$\phi(N)$。在当前的RSA标准和应用中公钥和私钥指数被定义为在模$\lambda(N)$下互为逆元即可。

\begin{align} \phi(N) &=(p-1)(q-1)\\ &=gcd(p-1,q-1)lcm(p-1,q-1)\\ &=gcd(p-1,q-1)lcm(\lambda(p),\lambda(q))\\ &=gcd(p-1,q-1)\lambda(N) \end{align}

• 在一般的讨论中，考虑RSA加密实例就公私钥指数的生成就两种情况：
  • 要么就是公私钥指数在$\lambda(N)$下互为逆元
  • 要么就是公私钥指数在$\phi(N)$下互为逆元

平衡素数

• 在一般的RSA加密中，只考虑平衡素数的情况，平衡素数其实就是两个RSA的二进制位数是相同的，其实就是p、q都是512位的二进制素数，不讨论p的二进制位数为512，而q的二进制位数为300这种情况（当然有的密码分析题目是会讨论的。）
• 这样对于$p、q$以及$N=pq$来说就有如下的一个不等式关系：

$$4<\frac{1}{2}N^{\frac{1}{2}}<p<N^{\frac{1}{2}}<q<2N^{\frac{1}{2}}$$

• 在这种平衡素数的情况下，$N$与$\phi(N)$的差值也满足一个不等式关系，不妨假设$p<q<2p$，推导如下：

\begin{align} |N-\phi(N)|&=|N-(p-1)(q-1)|\\ &=|N-(N-p-q+1)|\\ &=|p+q-1|\\ &<N^{\frac{1}{2}}+2N^{\frac{1}{2}}=3N^{\frac{1}{2}} \end{align}

• 因此其实可以得到一个结论：模数$N$和$\phi(N)$在二进制表示的高位部分有大量重合，比特结构高度相关（大概占N位数的一半）,因为两数相减后的结果是小于$3N^{\frac{1}{2}}$的。

  • 像这样高位部分有大量重合，比特结构高度相关也被叫做最高有效位(MSB Most Significant Bit)
  • 与之对应的低位部分有大量重合，比特结构高度相关也被叫做最低有效位(LSB Least Significant Bit)

• 由此就使用字母$s$表示差值：

$$s:=N-\phi(N)=p+q-1<3N^{\frac{1}{2}}$$

非形式化算法描述

• 使用非形式化的算法描述RSA的这个公钥密码系统，对RSA加密算法做出如下定义：

  • 密钥生成：
    • 随机生成两个平衡素数$p、q$，并计算他们的乘积，$N=pq$，其中$N$是n比特的模数。
    • 选择一个公钥指数$e$，公钥指数必须满足与$p-1$和$q-1$互素。
    • 接下来利用$ed\equiv1~mod(~\lambda(N))$或者是$ed\equiv 1~mod(~\phi(N)~)$，计算出私钥$d$
    • 算法输出公钥对$(e,N)$和私钥对$(d,p,q)$
    • 这个算法可以选择性的接受更多的参数，用于指定公私钥的大小。在这种情况下，一旦素数生成完成，就随机选取满足所指定大小的公钥指数，而另一个指数则通过逆元计算得到
  • 加密过程：加密算法使用公钥对$(e,N)$，明文$m=Z_N$，输出的是密文$c=m^e~mod(~N)$
  • 解密过程：解密算法使用私钥对$(d,p,q)$，密文$c=Z_N$，输出的是$m=c^d~mod(~N)$

• 还需要特别注意的就是，每当其中一个指数由另一个指数通过取模逆元的方式计算得到，这个指数非常大的概率将会是满位数或满尺寸（这个指数与$\phi(N)$或者是$\lambda(N)$位数相同）。

  • 例如，当指数是模$\phi(N)$下的逆元，一个满位的指数将大致与$\phi(N)$相同。由于$N$与$\phi(N)$具有相同的位数，因此可以推出，满尺寸指数在规模上大致与RSA模数相当。
  • 即使指数可能是在模$\lambda(N)$下的逆元，大概率生成的也是满位的一个指数。因为在随机生成RSA素数的情况下，$\lambda(N)$有很高的概率与$\phi(N)$具有近似相同的位数。
  • 简单说其实就是$\phi(N)$与$\lambda(N)$的位数在期望意义下非常接近。

• 其实也可以构造同时具有小公钥指数和小私钥指数的RSA实例，然而一般情况下仅考虑至多只有一个小指数较小的RSA实例。

• 注意：我们所研究的RSA密码分析学与实际工程中的差别还是比较大的。实际工程中会采用例如PKCS #1等工业标准，并配合使用随机化填充方案，这些填充能防止某些攻击。

RSA的安全

• RSA的安全性依赖于解决RSA问题的困难性，RSA问题(RSA problem)描述如下：给一个RSA公钥对$(e,N)$和密文$c=m^e~mod(~n)$，RSA问题是计算明文$m$。本质上就是求模$N$意义下的e次方根，或者说是对RSA函数进行求逆操作。

• 由于目前无法确定RSA问题在理论上的真实难度，因此我们实际上依赖于一个关于其困难性的假设。这个假设被称为RSA假设(RSA assumption)，其断言：当明文$m\in Z_N$是随机选择的，且模数足够大并由随机生成的素数组成时，RSA问题是难以求解的。

从RSA被提出以来，公开领域内尚无任何证据表明RSA假设是不成立的。

整数分解

• 另一个于RSA安全性普遍联系的问题其实就是著名的整数分解(Integer Factorization)问题。整数分解问题就是找到整数的一个非平凡因子。
• 如果RSA的模数能够被成功分解，那么对于任意的合法公钥指数$e$，都可以高效地计算出私钥指数d，这就使得使用公钥$(e,N)$加密后的数据都能被轻松解密。因此RSA问题的求解难度不会高于整数分解问题。（目前尚不清楚反过来是否成立，也就是是否能够通过求解RSA问题高效地解决整数分解问题。这是关于RSA的最重要的公开未解问题之一。）
• 已经有研究表明，对某些特定公钥指数，RSA问题可能比整数分解问题更容易求解，但是证件目前还不足。
• 尽管RSA问题在某些情况下可能确实比整数分解问题更容易，但在实际应用中，人们通常假设二者在安全性上是等价的。一个RSA实例的安全级别通常基于对其模数分解难度的估计。例如，使用当前已知最优的通解算法广义数域筛(GNFS General Number Field Sieve)，预计对一个1024位的模数进行分解大约需要$2^{80}$次运算。因此，通常认为1024位的RSA能提供与80位一次性密码本相当的安全强度。

破解RSA

• 对于破解一个密码系统，存在多种不同的定义，按照从难到易可以分为（这个顺序也是破解密码系统的严重程度）：

  • 完全破解(total break)：攻击者能够恢复完整的密钥，或者等价地对任意密文都能解出明文。
  • 部分破解(partial break)：攻击者无法完全解密，但可以从密文中恢复某些关于明文的非平凡信息。
  • 语义破解(semantic break)：攻击者可以区分两个等长明文的加密结果，即能在密文中获得任何与明文相关的优势信息。

• 由于整数分解问题包含了RSA问题，所以可以通过分解模数N来攻击RSA加密。整数分解问题是可以完全破解RSA加密的，因为分解出来N后我们就可以很快计算出私钥对。有以下几种方式可以分解N：

  • 可以使用已知的整数分解方法对该模数$N$进行分解。
  • 可以通过求私钥$d$的方法，分解模数$N$。
  • 可以通过求$\phi(N)$或者$\lambda(N)$的方法，分解模数$N$。

• 注解：根据上面这个我就对RSA加密的题型做出了分类

• 破解RSA加密有许多不同的方法，包括但不限于侧信道攻击、社会工程学攻击，社会工程学攻击这里不讨论，侧信道攻击如下：

  • 故障注入攻击
  • 时间攻击
  • 功耗分析攻击
  • 分支分析攻击

• 但是对于大部分CTF密码题来说是脱离实际应用的物理环境的（有的时候可能会考到偏实战的侧信道攻击），但是目前我学习的RSA攻击方式都是基于RSA密码体制的数学结构，并利用了某些特定的参数选择（比如：小公钥指数或者小私钥指数）。甚至还有一些部分私钥攻击，这种情况只关心已知部分私钥如何攻击RSA，而不关系这个部分私钥是如何获取的（一般要社工或者侧信道获取可能吧。）

RSA的同态性

• 如果不太了解同态加密的话，可以先跳过这个，所谓同态加密其实就是可以在密文上进行加法运算（或者是乘法运算），而解密后的明文其实是密文对应明文的乘法运算。
• 对于RSA加密来说，我们有两个明文$m_1、m_2$，我们可以得到$m=m_1m_2$。接下来我们对这三个明文进行加密操作可以得到：

$$c_1 = m_1^e~mod(~N)\\c_2=m_2^e~mod(~N)\\c = m^e~mod(~N)$$

• 对于这三个加密后的密文其实仍然会保持乘法关系，也就是说使用相同公钥对生成的密文进行乘法运算，解密后得到的明文也相当于是两个明文进行乘法运算得到的结果。

$$c_1*c_2=m_1^em_2^e=(m_1m_2)^e=m^e~mod(~N)$$

• 因为RSA加密具有的同态性，这就使得RSA加密在面对选择密文攻击的时候是不安全的。以下是两种攻击策略：

  • 攻击1：给出了密文$c=m^e~mod(~N)$，要我们求出明文$m$。并且攻击者可以主动选择任意密文，可以向服务器提供解密服务，可以将解密后得到的明文发送给攻击者，但是如果尝试解密$c$就会导致错误。攻击者已知，密文$c$，公钥对$(e,N)$，攻击方法如下：
    • 随机选择一个$x\in Z_n$，直接计算出$c_0=cx^e~mod(~N)$的值，并且将这个值发送给服务器。
    • 服务器对$c_0$进行解密操作，可以得到$m_0=c_0^d~mod(~N)=(cx^e)^d~mod(~N)=c^dx^{ed}~mod(~N)=mx~mod(~N)$，并将其发送给攻击者
    • 攻击者可以很快的计算出$m=m_0x^{-1}~mod(~N)$，从而恢复出明文。
  • 攻击2：该攻击相当于一个中间相遇攻击，假设目标明文是$L$位的明文$m$，该明文能被分解称为两个$\frac{L}{2}$位的因子$m_1$和$m_2$也就是$m=m_1m_2$。服务也是提供解密服务，攻击者传入密文给服务器，服务器计算出明文并返回给攻击者。攻击者已知$m$对应的密文$c$，以及公钥对$(e,N)$，要求的就是明文$m$。
    • 首先构造一张表，里面存储着可能的$\frac{L}{2}$位数的$m_1$及其加密之$m_1^e~mod(~N)$。
    • 随后，对每一个可能的$\frac{L}{2}$位数的$m_2$，计算并检查$c·m_2^{-e}~mod(~N)$是否与某个加密之相匹配。
    • 当$m_2=m_2^{*}$的时候就有$c·m_2^{-e}~mod(~N)=(m_1m_2)^e·m_2^{-e}~mod(~N)=m_1^e~mod(N)$必然在表中会出现。这样就可以计算得到$m$。

• 在实际应用中，使用恰当的填充规则，例如OAEP填充规则，就足够避免这些攻击了。

语义安全性

• 语义安全密码系统指的就是：给定一个密文及其公钥，攻击者无法以显著概率（non-negligible probability）推断出任何关于对应明文的信息。简单来说，语言安全性偏向判断或者获取一些信息，例如判断两个密文$c_1,c_2$哪个密文是由明文$m$通过RSA加密得到的。
• 我们上面说的没有进行填充等处理的原始RSA加密并不是语义安全的密码系统。特别地，任何确定性的密码系统都不可能是语义安全的。给定两个明文消息和其中一个密文，攻击者总是可以判断哪个明文对应该密文。因此，任何语义安全的密码系统都必须是概率性的。
• 此外对于RSA加密，可以很容易证明，明文的雅可比符号（以及模数）可以通过密文的雅可比符号暴露出来。具体而言，对于任意明文$m$及其对应密文$c$，有：

$$(\frac{c}{N})=(\frac{m}{N})$$

• 因此，仅凭密文和公钥就能泄露部分明文信息。当然使用OAEP填充的RSA加密，在RSA假设成立的前提下，可以证明其是语言安全的。

RSA效率

• 对于RSA加密的效率，主要考虑的就是素数生成和模幂运算的计算开销，这两者分别是密钥生成算法和加密解密算法中的主要操作。

• RSA密钥生成算法：

  • 需要生成的两个随机平衡素数，使用Miller-Rabin素性测试结合试除法。
  • 生成一个n位随机素数，其期望运行时间为$O(\frac{n^4}{log(n)}+tn^3)$
  • 该方法输出复合数而非素数的概率最多为$4^{-t}$。
  • 上述复杂度假设使用的是简单的二次运算，通过使用更快的乘法方法可以有所改进，但采用已知最快的方法生成n位素数，其复杂的也至少为$O(n^2)$。
  • 对于较大的模数，这可能是一个昂贵的操作，尤其是在需要生成大量素数的情况下。

• 对于RSA加密的模幂操作运算效率就这里暂时不说了。

RSA数字签名

RSA原语同时可以被用于构建加密方案和数字签名方案。本质上，简化地说，解密操作可以用来对文档进行签名，而加密操作可以用来验证数字签名。

RSA变种

• 在RSA专利中，三个RSA的发明人Rivest、Shamir 和 Adleman 提到：可以使用三个或者更多素数（不一定互不相同）相乘得到。解密分别可以分别对n的每一个素因子进行，然后利用中国剩余定理或任何等效方法将结果组合起来，从而得到对n的最终结果。
• 因此，从RSA发明以来，对RSA的变种创造也已经存在了，研究RSA变种的主要原因是以某种方式提高RSA的效率。
  • CRT-RSA、多素数RSA、多幂RSA：都是为了更快的生成密钥和更快的解密。
  • 共素数RSA：抵抗已知的RSA攻击。
  • 对偶RSA：降低存储公钥和私钥所需的内存空间。
  • 还有比较多的RSA变体可以自行了解，包括但不限于Rabin加密算法、使用Dickson 多项式的RSA加密算法、使用Lucas 数列的RSA加密算法

RSA攻击数学基础

• 对于密码分析学的数学要求，会比学密码编码学的数学要求高一点，而且也比较杂。这边建议对于初学者来说学一点数学知识，然后再学一点密码分析学的攻击手法，用密码分析学的攻击手法来理解所学的数学知识会好点。这样就不会因为前期花太多时间在数学上，也不会导致到后面的密码分析学需要的数学知识比较深和多而停滞不前。缺点就是每个攻击手法学的比较慢就是了，并且有的可能还得跳过之后再学（其实有的只需要会用脚本就行，原理之后再说。）

• 这里先列出RSA攻击所涉及的一些数学知识，顺便也需要学点算法：

  • 初等数论（先学），高等代数（最好直接学高等代数，别看线性代数了），格密码入门。
  • 抽象代数，代数数论，交换代数，解析数论，数的几何。
  • 认知有限无法推荐更多内容。

• 现在就列出一些RSA密码分析学中涉及到的一些数学概念和结论：

  • 数学概念：集合、向量、多项式、渐进符号、连分数、格（数学中有两种格，我们所说的是向量空间的那个格）
  • 数学结论：中国剩余定理（初等数论）、斯密特正交化（高等代数）、结式（高等代数）、连分数逼近定理（初等数论）
  • 算法：整数分解、格基规约算法（包括LLL算法等）、最短向量问题（格）
  • 其他：解线性方程、模线性等式、Coppersmith方法以及一堆相关的多项式、计算和改进边界。