介绍 RSA 的文章很多, 这里打算写一点能看得懂的文章

基本知识

为什么可靠? 对极大整数做因数分解是很困难的。

秘钥: 公钥(长度,公因数1) 私钥(长度,公因数2)

甲乙加密数据:

甲方传递消息给乙, 获取乙方公钥加密数据, 把数据交给乙, 乙用秘钥解密 乙方传递消息给甲, 获取甲方公钥加密数据, 把数据交给甲, 甲用秘钥解密

举例:

  1. 随机选择互质数 p=7, q=32 (如果不选择互质数的话, 随便一个数字反推质数, 因数分解那就比较难了, 我们先选好互质数, 方便欧拉函数计算)
  2. 计算一下他们乘积 n = p*q = 224
  3. 计算乘积数下面的质数有几个: 满足第四种欧拉方式

    φ(n) = φ(p1p2) = φ(p1)φ(p2)
       
    φ(224) = φ(7)*φ(32) = (7-1) * φ(2^5) = 6 * 32(1-1/2) = 96
    
    解释下224的计算方法, 
    7为质数, 所以φ(7) =7-1
    32为质数2的5次方, 符合通用公式 φ(32) = 32 * (1-1/2)
    
    

互质

如果两个正整数,除了1以外,没有其他公因子,我们就称这两个数是互质关系(coprime)。比如,15和32没有公因子,所以它们是互质关系。这说明,不是质数也可以构成互质关系。

关于互质关系,不难得到以下结论:

  1. 任意两个质数构成互质关系,比如13和61。
  2. 一个数是质数,另一个数只要不是前者的倍数,两者就构成互质关系,比如3和10。
  3. 如果两个数之中,较大的那个数是质数,则两者构成互质关系,比如97和57。
  4. 1和任意一个自然数是都是互质关系,比如1和99。
  5. p是大于1的整数,则p和p-1构成互质关系,比如57和56。
  6. p是大于1的奇数,则p和p-2构成互质关系,比如17和15。

欧拉函数(互质关系个数)

请思考以下问题:

任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?(比如,在1到8之中,有多少个数与8构成互质关系?)

欧拉函数就是计算个数的一个函数, 感兴趣的可以找下资料了解下

其中p1, p2……pn为x的所有质因数,x是不为0的整数。
φ(n) = n(1-1/p1)(1-1/p2)

解释一下:

  1. n 为质数,
     φ(n) = n - 1
    
  2. n 不为质数, 如21,
     φ(n) = φ(3*7)  3和7 都是质数, 参考第一条 φ(n) = (3-1)* (7-1) =12 
    
  3. 通用公式 φ(n) = n(1-1/p1)(1-1/p2)

     先知道质数情况下计算φ(n)
     37 * 7 = 259
     φ(259) = (37-1)(7-1) = 216
        
     不知道质数组成, 任意一个大于1的正整数,都可以写成一系列质数的积
     φ(1323) = φ(3^3*7^2) = 1323 * (1-1/3) * (1-1/7) = 756
        
     这个公式就比上面的复杂, 需要计算公因数(greatest common divisor)
        
    

golang 利用公因数 计算φ(n)个数

package main

import (
	"fmt"

)

// greatest common divisor (GCD) via Euclidean algorithm
func GCD(a, b uint) uint {
	for b != 0 {
		t := b
		
		b = a % b
		a = t
	}
	return a
}

// Eulers Totient Function
func Phi(n uint) uint {
	var result uint = 1
	var i uint
	for i = 2; i < n; i++ {
		if GCD(i, n) == 1 {
			result++
		}
	}
	return result
}

func main() {
	
	fmt.Println(Phi(uint(33)))
	
}

欧拉定理

如果两个正整数a和n互质,则n的欧拉函数 φ(n) 可以让下面的等式成立:

a^φ(n) - 1 = mod(n)

解释一下:

a的φ(n)次方可以被 (n +1) 整除

模反元素

如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。

这时,b就叫做a的”模反元素”。

ab === 1 (mod n)