RSA算法

Reference

Intro

非对称加密算法

核心: 加密秘钥(公钥)与解密密钥(私钥)不同

一般的非对称加密算法应用过程

  1. 甲欲传密信给乙, 乙先根据算法算出本次通信的公钥和私钥
  2. 乙将公钥传给甲
  3. 甲使用公钥加密原文m为密文c
  4. 乙使用私钥解密c为m

数学原理

质数与互质数

模运算

同余

如果两整数$a,b$满足$(a-b)\mod m=0$, 那么就称$a$与$b$对模$m$同余, 记作

欧拉函数

$\varphi(n)$为小于等于n的正整数中与$n$互质的个数

  1. 如果$n$可以分解为两个互质的整数之积, 即$n=p\times q$, 则有: $\varphi(n)=\varphi(p)\varphi(q)$
  2. 如果一个数是质数, 则: $\varphi(p)=p-1$

故, 若一个数$n=p\times q$, $p, q$都为质数, 则: $\varphi(n) = (p-1)()(q-1)$

欧拉定理

如果$a,n$互质, 则:

证明

剩余系定理2

剩余系定理5

模反元素

令$b=a^{\varphi(n)-1}$, 则有:

$b$就是$a$的模反元素, 即给定$a,n$互质, 必能找到它们的模反元素, 为$a^{\varphi(n)-1}$

费马小定理

令欧拉定理中$n$为素数$p$, 得

RSA算法

密钥计算方法

  1. 选取两个不相等质数$p$和$q$, (61, 53)
  2. 计算$n=p\times q=61\times 53=3233$
  3. 根据$\varphi(n)=(p-1)(q-1)$得$\varphi(3233)=3120$
  4. 随机选取一个整数$e$, $1<e<\varphi(n),(e,\varphi(n))=1$, 选择$17$
  5. 因为$e$和$\varphi(n)$互质, 设$d$为$e$关于$\varphi(n)$的模反元素, $ed\equiv 1(mod \quad \varphi(n))$
    即$ed-1=k\varphi(n)$
    取一组解$d=2753,k=-15$
  6. $(n,e)$为公钥, $(n,d)$为私钥

使用例子

  1. 甲欲发送$m=65$给乙
  2. 乙发送公钥$(n,e)=(3233,17)$给甲
  3. 甲根据以下公式加密$m$为$c$
    $m^e\equiv c(mod \quad n)$
    $c=m^e\mod n=65^{17}\mod 3233=2790$
  4. 乙收到密文$c=2790$, 使私钥$(n,d)=(3233,2753)$解密
    $c^d\equiv m(\mod n)$
    $m=c^d\mod n=2790^{2753}\mod 3233=65$

为什么$(x^e)^d\equiv 1\mod n$

文章目录
  1. 1. Reference
  2. 2. Intro
  3. 3. 非对称加密算法
  4. 4. 数学原理
    1. 4.1. 质数与互质数
    2. 4.2. 模运算
    3. 4.3. 同余
    4. 4.4. 欧拉函数
    5. 4.5. 欧拉定理
    6. 4.6. 模反元素
    7. 4.7. 费马小定理
  5. 5. RSA算法
    1. 5.1. 密钥计算方法
    2. 5.2. 使用例子
    3. 5.3. 为什么$(x^e)^d\equiv 1\mod n$
|