math/discrete_math/4-Number-Theory-and-Cryptography.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第4章 数论和密码学\n",
    "## 4.1 整除性和模算术\n",
    "### 4.1.2 除法\n",
    "**定义1**：如果a和b是整数且$a \\ne 0$，我们称a整除b如果有整数c使得b=ac，或者等价地，如果$\\frac{b}{a}$是一个整数。当a整除b时，我们称a是b的一个因子或除数，而b是a的一个倍数。用记号$a \\mid b$表示a整除b。当a不能整除b时则写成$a \\nmid b$。\n",
    "\n",
    "评注：可以用量词把$a \\mid b$表示成($\\exists c(ac=b)$)，其中论域是整数集合。\n",
    "\n",
    "**定理1**：令a，b，c为整数，其中$a \\ne 0$。则\n",
    "\n",
    "1. 如果a|b和a|c，则a|(b+c)。\n",
    "2. 如果a|b，那么对所有整数c都有a|bc。\n",
    "3. 如果a|b，b|c，则a|c。\n",
    "\n",
    "**推论1**：如果a，b，c是整数，其中$a \\ne 0$，使得a|b和a|c，那么当m和n是整数时有a|mb+nc。\n",
    "\n",
    "### 4.1.3 除法算法\n",
    "**定理2 除法算法（division algorithm）**：令a为整数，d为正整数，则存在唯一的整数q和r，满足$0 \\le r < d$，使得a=dq+r。\n",
    "\n",
    "**定义2**：在除法算法的等式中，d称为是除数，a称为是被除数，q称为是商，r称为是余数。下面的记号用来表示商和余数。\n",
    "\n",
    "q = a div d,r = a mod d\n",
    "\n",
    "### 4.1.4 模算术\n",
    "**定义3**：如果a和b为整数而m为正整数，则当m整除a-b时称a模m同余b。用记号$a \\equiv b(mod\\ m)$表示a模m同余b。我们称$a \\equiv b(mod\\ m)$为**同余式**（congruence），而那个m是它的**模**（modulus）。\n",
    "\n",
    "**定理3**：令a和b为整数，并令m为正整数，则$a \\equiv b(mod\\ m)$当且仅当a mod m = b。\n",
    "\n",
    "**定理4**：令m为正整数。整数a和b是模m同余的当且仅当存在整数k使得a=b+km。\n",
    "\n",
    "**定理5**：令m为正整数。如果$a \\equiv b(mod\\ m),c \\equiv d(mod\\ m)$，则$a+c \\equiv b+d(mod\\ m)$并且$ac \\equiv bd(mod\\ m)$。\n",
    "\n",
    "推理2：令m是正整数，令a和b是整数。则\n",
    "\n",
    "(a+b) mod m = ((a mod m) + (b mod m)) mod m\n",
    "\n",
    "并且\n",
    "\n",
    "ab mod m = ((a mod m)(b mod m)) mod m。\n",
    "\n",
    "### 4.1.5 模m算术\n",
    "$a+_m b=(a+b)\\ mod\\ m$\n",
    "\n",
    "$a\\cdot_m b=(a \\cdot b)\\ mod\\ m$\n",
    "\n",
    "运算符$+_m$和$\\cdot_m$满足这些性质：\n",
    "\n",
    "- 封闭性：如果a和b属于$Z_m$，则$a +_m b$和$a \\cdot_m b$也属于$Z_m$。\n",
    "- 结合律：如果a，b和c属于$Z_m$，则有$(a+_m b) +_m c = a+_m(b +_m c)$和$(a \\cdot_m b)\\cdot_m c = a \\cdot_m (b \\cdot_m c)$。\n",
    "- 交换律：如果a和b属于$Z_m$，则$a +_m b = b +_m a$和$a \\cdot_m b=b \\cdot_m a$。\n",
    "- 单位元：元素0和1分别是模m加法和乘法的单位元。即如果a属于$Z_m$，则$a +_m 0=a$和$a \\cdot_m 1=a$。\n",
    "- 加法逆元：如果$a \\ne 0$属于$Z_m$，则m-a时a的模m加法逆元，而0是其自身的加法逆元。即$a +_m (m-a)=0$且$0 +_m 0=0$。\n",
    "- 分配律：如果a，b和c属于$Z_m$，则$a \\cdot_m (b +_m c) = (a \\cdot_m b) + (a \\cdot_m c)$和$(a +_m b) \\cdot_m c=(a \\cdot_m c) +_m (b \\cdot_m c)$。\n",
    "\n",
    "评注：因为带有模m加法和乘法运算的$Z_m$满足上面所列的性质，所以$Z_m$连同模加法被称为一个**交换群**，而$Z_m$连同这两个运算被称为一个**交换环**。注意整数集合加上普通的加法和乘法也构成一个交换环。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.2 整数表示和算法\n",
    "### 4.2.2 整数表示\n",
    "**定理1**：令b是一个大于1的整数。则如果n是一个正整数，就可以唯一地表示为下面的形式：$n=a_kb^k+a_{k-1}b^{k-1}+\\cdots+a_1b+a_0$，其中k是非负整数，$a_0,a_1,\\cdots,a_k$是小于b的非负整数，且$a_k \\ne 0$。\n",
    "\n",
    "定理1给出的n的表示称为**n的b进制展开式**。\n",
    "\n",
    "**进制转换算法**：构造一个整数n的b进制展开式。首先，用b除n得到商和余数，即$n=bq_0+a_0,0 \\le a_0 < b$\n",
    "\n",
    "余数$a_0$就是n的b进制展开式中最右边的数字。下一步用b除$q_0$得$q_0=bq_1+a_1,0 \\le a_1 < b$\n",
    "\n",
    "可以看出$a_1$是n的b进制展开式中从右边第二位数字。继续这一过程，连续用商数除以b并以余数为新的b进制数字。这一过程在商为0时终止。该过程从右向左产生n的b进制数字。\n",
    "\n",
    "### 4.2.3 整数运算算法\n",
    "**加法算法**：通过把对应位的二进制数字相加，当产生进位时再加上进位，从而计算两个整数的和。\n",
    "\n",
    "要把a和b想加，首先把最右边的位相加。这样可得 $a_0+b_0=c_0 \\cdot 2 + s_0$\n",
    "\n",
    "其中$s_0$是a+b的二进制展开式中最右边的一位数字，而$c_0$是进位，$c_0$为0或1.然后把下一对二进制位及进位相加，$a_1+b_1+c_0=c_1 \\cdot 2 + s_1$\n",
    "\n",
    "其中$s_1$是a+b的二进制展开中的下一位（从右算起）数字，$c_1$是进位。继续这一过程，把两个二进制展开式中对应的二进制位及进位相加，给出a+b的二进制展开式中从右算起的下一位数字。最后，把$a_{n-1},b_{n-1},c_{n-2}$相加得$c_{n-1} \\cdot 2 + s_{n-1}$。和的首位数字是$s_n=c_{n-1}$。这一过程产生a与b之和的二进制展开式，即$a+b=(s_ns_{n-1}s_{n-2}\\cdots s_1s_0)_2$。\n",
    "\n",
    "**乘法算法**：考虑两个n位整数a和b的乘法。利用分配律，可以看出\n",
    "\n",
    "$ab=a(b_02^0+b_12^1+\\cdots+b_{n-1}2^{n-1})=a(b_02^0)+a(b_12^1)+\\cdots+a(b_{n-1}2^{n-1})$\n",
    "\n",
    "可以用这一等式来计算ab。\n",
    "\n",
    "**div和mod算法**：给定整数a和d，d>0，计算q=a div d和r=a mod d。在这个蛮力算法中，当a为正时，就从a中尽可能多次减去d，直到剩下的值小于d为止。所做减法的次数就是商而最后减剩下的值就是余数。\n",
    "\n",
    "### 4.2.4 模指数运算\n",
    "利用n的二进制展开式，比如$n=(a_{k-1}\\cdots a_1a_0)_2$，来计算$b^n$。首先，注意$b^n=b^{a_{k-1}\\cdot 2^{k-1}+\\cdots+a_1\\cdot 2 + a_0}=b^{a_{k-1}\\cdot 2^{k-1}}\\cdots b^{a_1\\cdot 2}\\cdot b^{a_0}$\n",
    "\n",
    "这就说明了为了计算$b^n$的值，只需要计算$b,b^2,(b^2)^2=b^4,(b^4)^2=b^8,\\cdots,b^{2^{k-1}}$的值。一旦有了这些值，把列表中$a_j=1$的那些项$b^{2^j}$相乘。这就可以得到$b^n$的值。\n",
    "\n",
    "该算法依次求出b mod m,$b^2$ mod m,$b^4$ mod m,...,$b^{2^{k-1}}$ mod m，并把其中$a_j=1$的那些项$b^{2^j}$ mod m相乘，在每次乘法后求乘积除以m所得的余数。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.3 素数和最大公约数\n",
    "### 4.3.2 素数\n",
    "**定义1**：大于1的整数p称为素数，如果p的正因子只是1和p。大于1但又不是素数的正整数称为合数。\n",
    "\n",
    "评注：整数n是合数当且仅当存在整数a使得a|n并且1 < a < n。\n",
    "\n",
    "**定理1 算术基本定理**：每个大于1的整数都可以唯一地写为两个或多个素数的乘积，其中素数因子以非递减序列排列。\n",
    "\n",
    "### 4.3.3 试除法\n",
    "**定理2**：如果n是一个合数，那么n必有一个素因子小于或等于$\\sqrt{n}$。\n",
    "\n",
    "从定理2可知，如果一个整数不能被小于或等于其平方根的素数整除，则它就是素数。这一结论导致了称为试除法的蛮力算法。要用试除法，我们把n除以所有不超过$\\sqrt{n}$的素数，如果不能被其中任意一个素数整除就可以得出结论n是素数。\n",
    "\n",
    "### 4.3.4 埃拉托斯特尼筛法\n",
    "注意，不超过100的合数必定有一个不超过10的素因子。因为小于10的素数仅有2、3、5和7，所以不超过100的素数就是这四个素数以及那些大于1且不超过100同时不能被2、3、5和7之一整除的正整数。\n",
    "\n",
    "下列过程寻找不超过100的素数：首先构造1~100全部整数列表。筛法开始过程，除了2以外，删除那些能被2整除的整数。因为3是保留下来的第一个大于2的整数，所以除了3以外，删除所有那些能被3整除的整数。因为5是3之后保留下来的下一个整数，所以除了5以外，删除那些能被5整除的整数。保留下来的下一个数是7，所以，除了7以外，删除那些能被7整除的整数。因为所有不超过100的合数能被2、3、5或7整除，所以除了1以外，所有保留下来的整数都是素数。\n",
    "\n",
    "**定理3**：存在无限多个素数。\n",
    "\n",
    "**定理4（素数定理）**：当x无限增长时，不超过x的素数个数与x/Inx之比趋近于1。\n",
    "\n",
    "可以用素数定理来估计随机选择的一个数是素数的可能性。素数定理告诉我们不超过x的素数个数可以用x/Inx来逼近。因此，一个随机选择的正整数n是素数的可能性大约是 $\\frac{(n/In n)}{n}=\\frac{1}{In n}$。\n",
    "\n",
    "**素数和算术级数**：每个奇整数都在下面两种算术级数之中4k+1或者4k+3，k=1,2,...。因为我们知道存在无限多个素数，所以我们会问是否在这两种算术级数中都有无限多个素数。素数5，13，17，29，37，41，...在算术级数4k+3中；而素数3，7，11，19，23，31，43，...则在算术级数4k+1中。那么如ak+b,k=1,2,...的算术级数会包含无限多个素数吗？答案由德国数学卷狄利克雷给出，他证明了每个这样的级数都包含无限多个素数。\n",
    "\n",
    "### 4.3.6 最大公约数和最小公倍数\n",
    "**定义2**：令a和b是两个整数，不全为0.能使d|a和d|b的最大整数d称为a和b的`最大公约数`。a和b的最大公约数记作gcd(a,b)。\n",
    "\n",
    "**定义3**：整数a和b互素的如果它们的最大公约数是1。\n",
    "\n",
    "**定义4**：整数$a_1,a_2,...,a_n$是两两互素的，如果当$1 \\le i < j \\le n$时有$gcd(a_i,a_j)=1$。\n",
    "\n",
    "**定义5**：正整数a和b的`最小公倍数`是能被a和b整除的最小正整数。a和b的最小公倍数记作lcm(a,b)。\n",
    "\n",
    "**定理5**：令a和b为正整数，则$ab=gcd(a,b) \\cdot lcm(a,b)$\n",
    "\n",
    "### 4.3.7 欧几里得算法\n",
    "**引理1**：令a=bq+r，其中a，b，q和r均为整数。则gcd(a,b)=gcd(b,r)。\n",
    "\n",
    "### 4.3.8 gcd的线性组合表示\n",
    "**定理6（贝祖定理）**：如果a和b为正整数，则存在整数s和t使得gcd(a,b)=sa+tb。\n",
    "\n",
    "**定义6**：如果a和b为正整数，则使得gcd(a,b)=sa+tb的整数s和t称为a和b的贝祖系数。还有，等式gcd(a,b)=sa+tb称为贝祖恒等式。\n",
    "\n",
    "换句话说，gcd(a,b)可以表示为a和b的整系数的**线性组合**。\n",
    "\n",
    "**引理2**：如果a，b和c为正整数，使得gcd(a,b)=1且a|bc，则a|c。\n",
    "\n",
    "**引理3**：如果p是素数，且$p|a_1a_2\\cdots a_n$，其中$a_i$为整数，则对于某个i，$p|a_i$。\n",
    "\n",
    "**定理7**：令m为正整数，令a，b和c为整数。如果$ac \\equiv bc$(mod m)且gcd(c,m)=1，则$a \\equiv b$(mod m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.4 求解同余方程\n",
    "### 4.4.2 线性同余方程\n",
    "具有下面形式的同余方程：$ax \\equiv b$(mod m)\n",
    "\n",
    "其中m为正整数，a和b为整数，x为变量，称为`线性同余方程`。\n",
    "\n",
    "使得$\\bar{a}a \\equiv 1$(mod m)成立的整数$\\bar{a}$，如果这样的整数存在，则$\\bar{a}$称为a模m的`逆`。当a和m互素时，定理1能保证a模m的逆存在。\n",
    "\n",
    "**定理1**：如果a和m为互素的整数且m>1，则a模m的逆存在。再者，这个模m的逆是唯一的。（即，存在唯一小于m的正整数$\\bar{a}$是a模m的逆，并且a模m的其他每个逆均和$\\bar{a}$模m同余。）\n",
    "\n",
    "寻找3模7的逆：$5 \\cdot 3 \\equiv 1$(mod 7)，所以5就是3模7的一个逆。\n",
    "\n",
    "### 4.4.3 中国剩余定理\n",
    "**定理2**：中国剩余定理。令$m_1,m_2,\\cdots,m_n$为大于1的两两互素的正整数，而$a_1,a_2,\\cdots,a_n$是任意整数。则同余方程组\n",
    "\n",
    "$$x \\equiv a_1(mod\\ m_1)$$\n",
    "\n",
    "$$x \\equiv a_2(mod\\ m_2)$$\n",
    "\n",
    "$$\\vdots$$\n",
    "\n",
    "$$x \\equiv a_n(mod\\ m_n)$$\n",
    "\n",
    "有唯一的模$m=m_1m_2\\cdots m_n$的解。（即，存在一个满足$0 \\le x \\le m$的解x，而所有其他的解均与此解模m同余。）\n",
    "\n",
    "例如下列同余方程组的解为x=23(最小正整数解)\n",
    "\n",
    "$$x \\equiv 2(mod\\ 3)$$\n",
    "\n",
    "$$x \\equiv 3(mod\\ 5)$$\n",
    "\n",
    "$$x \\equiv 2(mod\\ 7)$$\n",
    "\n",
    "### 4.4.4 大整数的计算机算术\n",
    "假设$m_1,m_2,\\cdots,m_n$是两两互素的模数，并令m为其乘积。根据中国剩余定理可以证明满足$0 \\le a < m$的整数a可唯一地表示为一个n元组，其元素由a除以$m_i$的余数组成，$i=1,2,\\cdots,n$。即，a可以唯一地表示为\n",
    "\n",
    "$$(a\\ mod\\ m_1,a\\ mod\\ m_2,\\cdots,a\\ mod\\ m_n)$$\n",
    "\n",
    "例8：假定在某台处理器上做小于100的整数算术运算比做大整数算术快得多。如果我们把整数表示为除以100以内两两互素的模的余数，就几乎可以将所有计算限制在100以内的整数上。例如，可以用99，98，97和95作为模数。（这些整数是两两互素的，因为没有大于1的公因子。）\n",
    "\n",
    "根据中国剩余定理，每个小于$99 \\cdot 98 \\cdot 97 \\cdot 95=89\\ 403\\ 930$的非负整数均可唯一地用该整数除以这四个模数的余数表示。例如，把123 684表示为(33,8,9,89)，因为123 684 mod 99=33, 123 684 mod 98=8,123 684 mod 97=9及123 684 mod 95=89。类似地，413 456可表示为(32,92,42,16)。\n",
    "\n",
    "欲求123 684和413 456的和，我们针对这些四元组而非直接针对这两个整数做运算。我们把四元组的对应分量相加，再按相应的模数压缩各分量。这样可得\n",
    "\n",
    "$$(33,8,9,89)+(32,92,42,16)$$\n",
    "\n",
    "$$=(65\\ mod\\ 99,100\\ mod\\ 98,51\\ mod\\ 97,105\\ mod\\ 95)$$\n",
    "\n",
    "$$=(65,2,51,10)$$\n",
    "\n",
    "要找出和，即(65,2,51,10)所表示的整数，需要求解同余方程组\n",
    "\n",
    "$$x \\equiv 65(mod\\ 99)$$\n",
    "\n",
    "$$x \\equiv 2(mod\\ 98)$$\n",
    "\n",
    "$$x \\equiv 51(mod\\ 97)$$\n",
    "\n",
    "$$x \\equiv 10(mod\\ 95)$$\n",
    "\n",
    "可以证明537 140是方程组唯一小于89 403 930的非负数。因此，537 140是所求的和。注意只有当我们需要恢复(65,2,51,10)所表示的整数时才必须做大于100的整数算术运算。\n",
    "\n",
    "### 4.4.5 费马小定理\n",
    "**定理3（费马小定理）**：如果p为素数，a是一个不能被p整除的整数，则\n",
    "\n",
    "$$a^{p-1} \\equiv 1(mod\\ p)$$\n",
    "\n",
    "再者，对每个整数a都有\n",
    "\n",
    "$$a^p \\equiv a(mod\\ p)$$\n",
    "\n",
    "评注：费马小定理告诉我们如果$a \\in Z_p$，则$a^{p-1}=1$也在$Z_p$中。\n",
    "\n",
    "例9：计算$7^{222}\\ mod\\ 11$。\n",
    "\n",
    "解：由费马小定理可知，$7^{10} \\equiv 1(mod\\ 11)$，所以对每个正整数k有$(7^{10})^k \\equiv 1(mod\\ 11)$。为了利用这最后一个同余式，我们将指数222除以10，得$222=22 \\cdot 10 + 2$。可以看出\n",
    "\n",
    "$$7^{222}=7^{22 \\cdot 10 + 2}=(7^{10})^{22}7^2 \\equiv (1)^{22} \\cdot 49 \\equiv 5(mod\\ 11)$$\n",
    "\n",
    "从而得$7^{222}\\ mod\\ 11=5$。\n",
    "\n",
    "### 4.4.6 伪素数\n",
    "**定义1**：令b是一个正整数。如果n是一个正合数且$b^{n-1} \\equiv 1$(mod n)，则n称为以b为基数的伪素数。\n",
    "\n",
    "**定义2**：一个正合数n如果对于所有满足gcd(b,n)=1的正整数b都有同余式$b^{n-1} \\equiv 1$(mod n)成立，则称为卡米切尔数。\n",
    "\n",
    "### 4.4.7 原根和离散对数\n",
    "**定义3**：模素数p的一个原根是$Z_p$中的整数r使得$Z_p$中的每个非零元素都是r的一个幂次。\n",
    "\n",
    "**定义4**：假设p是一个素数，r是一个模p的原根，而a是介于（含）1和p-1之间的一个整数。如果$r^e\\ mod\\ p=a$且$0 \\le e \\le p -1$，我们说e是以r为底a模p的离散对数，并写作$log_ra=e$（这里隐含理解为有素数p）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.5 同余应用\n",
    "### 4.5.1 离散函数\n",
    "最常用的离散函数之一是：h(k)=k mod m。\n",
    "\n",
    "### 4.5.2 伪随机数\n",
    "最常用的产生伪随机数的过程是`线性同余法`。选择4个整数：模数m、倍数a、增量c和种子$x_0$，满足$2 \\le a < m,0 \\le c < m,0 \\le x_0 <m$。通过连续应用下面递归函数来生成一个伪随机数序列{$x_n$}，满足对于所有n，$0 \\le x_n < m$:\n",
    "\n",
    "$$x_{n+1}=(ax_n+c)\\ mod\\ m$$\n",
    "\n",
    "### 4.5.3 校验码\n",
    "`奇偶校验码`：位串$x_1x_2\\cdots x_n$的奇偶校验位$x_{n+1}$定义为：\n",
    "\n",
    "$$x_{n+1}=x_1+x_2+\\cdots+x_n\\ mod\\ 2$$\n",
    "\n",
    "`UPC`(Universal Product Code)通用产品代码，最常用的形式是12位十进制数字：第一位数字标识产品种类，接着五位标识制造商，再五位标识特定产品，最后一位是校验码。校验码由同余式决定：\n",
    "\n",
    "$$3x_1+x_2+3x_3+x_4+3x_5+x_6+3x_7+x_8+3x_9+x_{10}+3x_{11}+x_{12} \\equiv 0(mod\\ 10)$$\n",
    "\n",
    "`ISBN`(International Standard Book Number,ISBN-10)国际标准书号，一个ISBN-10包含不同分组来标识语言、出版商、出版公司赋予图书的编号、最后一位校验码（或者数字或者字母X代表10）。这个校验码的选择满足：\n",
    "\n",
    "$$x_{10}=\\sum_{i=0}^9ix_i(mod\\ 11)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.6 密码学\n",
    "### 4.6.2 古典密码学\n",
    "`凯撒密码`：把字母表中的每个字母正向移动三位（字母表中的最后三个字母移到最开始的三个字母）。\n",
    "\n",
    "`加密`(encryption)就是对信息进行保密处理的过程。\n",
    "\n",
    "从加密消息中来确定原始消息的过程称为`解密`（decryption）。\n",
    "\n",
    "`移位密码`（扩展凯撒密码）把每个字母对应的数移动k位，而不是3位：f(p)=(p+k) mod 26。\n",
    "\n",
    "解密可以用：$f^{-1}(p)=(p-k)\\ mod\\ 26$。\n",
    "\n",
    "这里整数k成为`密钥`(key)。\n",
    "\n",
    "可以用下列形式的函数扩展移位密码以进一步加强安全性：f(p)=(ap+b) mod 26，其中a和b为整数，其选择需保证f是一个双射函数。（函数f(p)=(ap+b) mod 26是双射函数当且仅当gcd(a,26)=1.）这样的映射称为`仿射函数`。\n",
    "\n",
    "在不具有加密方法和密钥知识的情况下从密文中恢复出明文的过程称为`密码分析`或`破译密码`。\n",
    "\n",
    "移位密码和仿射密码是用字母表的一个字母来替换字母表中的另一个字母来实现的。因此，这些密码称为`字符`或`单码密码`。这种加密方法面对基于密文中字母频率分析的攻击是很脆弱的。通过用一组字母替换另一组字母而不是用单独的字母替换另一个字母的方式可以强化成功破译密文的难度，这样的密码称为`分组密码`(block cipher)。\n",
    "\n",
    "**定义1**：一个密码系统（cryptosystem）是一个五元组（P，C，K，E，D），这里P明文串的集合，C是密文串的集合，K是密钥空间，E是加密函数的集合，而D是解密函数的集合。我们用$E_k$表示在E中相对于密钥k的加密函数而$D_k$是D中用来解密由$E_K$加密的密文的解密函数，即对于所有明文串p有$D_k(E_k(p))=p$。\n",
    "\n",
    "### 4.6.3 公钥密码学\n",
    "所有古典密码，包括移位密码和仿射密码，都是`私钥密码系统`（private key cryptosystem）的实例。\n",
    "\n",
    "当采用私钥密码系统时，希望秘密通信的双方必须共享一个密钥。\n",
    "\n",
    "为了避免每对希望安全通信的双方都需要共享密钥，20世纪70年代密码学家引入了`公钥密码系统`（public key cryptosystem）的概念。当使用这种密码系统时，知道怎样发送加密消息的人并不能解密消息。\n",
    "\n",
    "### 4.6.4 RSA密码系统\n",
    "在RSA密码系统中，每个人都有一个加密密钥(n,e)，这里n=pq是一个由两个大素数，比如各有200位数字的p和q的乘积构成的模数，e是与(p-1)(q-1)互素的指数。n=pq大约400位数字，迄今为止不可能在合理的时间内被因子分解。\n",
    "\n",
    "### 4.6.5 RSA加密\n",
    "为了用特定的密钥(n,e)对消息加密：\n",
    "\n",
    "1. 将明文消息M翻译成整数序列，先将每个明文字母翻译成两位数；\n",
    "2. 将这些两位数连接起来构成数字串；\n",
    "3. 将这个串再分成2N位数字等长的分组，这里2N是一个大偶数使得2N位数字的整数2525...25不超过n。\n",
    "\n",
    "已经将明文消息M翻译成了一个整数序列$m_1,m_2,\\cdots,m_k$，k为整数。加密过程是将每个分组$m_i$转换成密文分组$c_i$。由下列函数实现\n",
    "\n",
    "$$C=M^e\\ mod\\ n$$\n",
    "\n",
    "所得加密后的消息依然是数的分组形式，所以这是一种分组密码。\n",
    "\n",
    "### 4.6.6 RSA解密\n",
    "当已知解密密钥d就是e模(p-1)(q-1)的逆时，就可以很快地从密文消息恢复出明文消息。\n",
    "\n",
    "$$C^d \\equiv M(mod\\ pq)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}