N1H111SM's Miniverse

RSA Algorithm

字数统计: 535阅读时长: 2 min
2020/03/06 Share


Euler’s totient function

Definition (Euler’s totient function). In number theory, Euler’s totient function $\phi(n)$ counts the positive integers up to a given integer $n$ that are relatively prime to $n$. The Euler’s totient function is computed by the following formula:

where the product is over the distinct prime numbers dividing $n$.


When $(n=1)$:

When $(n=p)$:

When $(n=p^k)$:

When $(n=p_1p_2)$:

因为任意一个整数$n$都能够表示成$n=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$的形式,所以根据以上四种情况的结论我们有:

Euler’s theorem

In number theory, Euler’s theorem (also known as the Fermat–Euler theorem or Euler’s totient theorem) states that if $n$ and $a$ are coprime positive integers, then

RSA Algorithm

The RSA algorithm involves four steps: key generation, key distribution, encryption and decryption.

A basic principle behind RSA is the observation that it is practical to find three very large positive integers $e$, $d$ and $n$ such that with modular exponentiation for all integers $ m$ (with 0 ≤ m < n):

上面的式子里,$e$ 是进行加密的public key, $d$ 是用来解密的private key。

Key generation

假设Alice和Bob是需要加密通信的两个主人公。Alice可以通过以下步骤生成public key & private key:

  • 选取两个大质数 $p$ 和 $q$,计算$N=pq$
  • 计算 $N$ 的欧拉函数值 $r=\varphi(N)=(p-1)(q-1)$
  • 找到一个小于 $r$ 并与 $r$ 互质的整数 $e$,同时求出 $e$ 关于 $r$ 的模的逆元,即 $ed \equiv 1 \pmod r$
  • 将两个大质数 $p, q$ 的记录销毁
  • 得到公钥$(N,e)$和私钥$(N,d)$。
  • 将公钥发送给Bob,Alice自己保管私钥不被公开。


Bob对明文 $m$ 通过公钥$(N,e)$进行加密并发送给Alice:


Alice将收到的密文 $c$ 通过私钥 $(N,d)$ 进行解密:

  1. 1. Euler’s totient function
    1. 1.1. Derivation
  2. 2. Euler’s theorem
  3. 3. RSA Algorithm
    1. 3.1. Key generation
    2. 3.2. Encryption
    3. 3.3. Decryption