辗转相除法求模的逆元

2019-04-13 12:48发布

最近研究RSA算法,发现在这个算法里,实现过程中的核心就是求出密钥D,求密钥的公式:
E*D ≡ 1 mod r ,现在已知了E和r,求E即是一个求模的逆元问题。 注:≡是数论中表示同余的符号。公式中,≡符号的左边必须和符号右边同余,也就是两边模运算结果相同。显而易见,不管r取什么值(r是N的欧拉函数值,N是大素数p与q的乘积),符号右边1 mod r 的结果都等于1;符号的左边d与e的乘积做模运算后的结果也必须等于1,即满足 (E*D)/mod r = 1 。
问题:
求A关于模N的逆元B,即要找出整数B,使A * B mod N = 1 (或A * B = x * N + 1),这里要求A与N互素。
方法:
辗转相除法(欧几里德算法)
-该算法原用于求两个数的最大公约数,经过变形可用于求模逆元
首先对余数进行辗转相除:
N = A * a0 + r0
A = r0 * a1 + r1
r0 = r1 * a2 + r2
r1 = r2 * a3 + r3

rn-2 = rn-1 * an + rn
rn-1 = rn * an+1 + 0 对上面的商数逆向排列(不含余数为0的商数):
在这里插入图片描述
其中:
b-1 = 1
b0 = an
bi = an-1 * bi-1 + bi-2
如果n为奇数(即商个数为偶数),则bn即为所求的逆元B;
如果n为偶数(即商个数为奇数),则N-bn即为所求的逆元B。

实践一下

求61关于模105的逆。先对余数辗转相除:
105 = 61 * 1 + 44
61 = 44 * 1 + 17
44 = 17 * 2 + 10
17 = 10 * 1 + 7
10 = 7 * 1 + 3
7 = 3 * 2 + 1
3 = 1 * 3 + 0
将商数逆序排列:
在这里插入图片描述
由于商的个数为偶数,因此31即为61关于模105的逆元。(31 * 61 = 105 * 18 + 1)
求31关于模105的逆,先对余数辗转相除:
105 = 31 * 3 + 12
31 = 12 * 2 + 7
12 = 7 * 1 + 5
7 = 5 * 1 + 2
5 = 2 * 2 + 1
2 = 1 * 2 + 0
将商数逆序排列:
在这里插入图片描述
由于商的个数为奇数,因此105-44=61即为31关于105的逆元。

辗转相除法求模逆元代的码实现

辗转相除法求判断互质

/***************************************************************************************************************** * 辗转相除法, 又名欧几里德算法(Euclidean algorithm),是求最大公约数的一种方法。它的具体做法是:用较小数除较大数, *再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是 *求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数 ——百度百科 *****************************************************************************************************************/ //Python //这段代码是使用辗转相除法求最大公约数,判断条件为:如果直到n=1才除尽,说明m、n互质,即最大公约数为1 #求最大公约数,若最大公约数是1,且m,n>1,m与n不等,则说明m,n互质 def comm_div(m, n): #m>n temp = m % n while(temp != 0): m = n n = temp temp = m % n if n == 1: #说明互质,返回True return True // C语言 #include <stdio.h> #include <stdlib.h> int pan_duan_hu_zhi(int* a, int* b) { int m,n,temp; m = *a; n = *b; temp = m % n; while(temp != 0) { m = n; n = temp; temp = m % n; } return n; } int main() { int a, b; int Flag = 0; //char ch,*arr,wei='a'; printf("请输入a、b值,用空格间隔开 "); scanf("%d%d", &a, &b); //从键盘获取a、b值 // 数据整理保证 m > n if(a<b) { Flag = a; a = b; b = Flag; Flag = 0; } Flag = pan_duan_hu_zhi(&a, &b); if(Flag == 1) printf("%d和%d互质 ",a,b); else printf("%d和%d的最大公约数为%d",a,b,Flag); getchar(); return 0; }

辗转相除法求模的逆

//Python 代码 #用辗转相除法求质数e关于欧拉公式F的逆元 def _e_product(e, F): a_list = [] m = F n = e temp = m % n while (temp != 0): a = (m - temp) / n a_list.append(a) m = n n = temp temp = m % n print("a_list:", a_list) a_list.reverse() #逆序 print("a_list_reverse:", a_list) b_list = [] b_list.append(1) b_list.append(a_list[0]) print("(最初插入的两个1及a_list[0])b_list:", b_list) for i in range(len(a_list)-1): b = b_list[-1] * a_list[i+1] + b_list[-2] b_list.append(b) print("b_list", b_list) #a_list存放的是商数,如果商数个数是偶数 b_list[-1]即为所求逆元 #若为奇数,F-b_list[-1]为所求的逆元 if len(a_list) % 2 == 0: #偶数 return b_list[-1] else: return F - b_list[-1] // C代码 // 代码写得比较烂,打印信息也不去了,多多包涵>_< #include <stdio.h> #include <stdlib.h> #include <memory.h>//要使用memset是要包含此头文件 int _E_Product (int* e, int* F) { int i, a, m, n, temp,j,k,D,f; int *p_quotient, *q_remainer, *p_quotient_reverse, *b_list; p_quotient = (int*)malloc(512*(sizeof(int*))); // 存放每轮计算得到的商 q_remainer = (int*)malloc(512*(sizeof(int*))); // 存放每轮计算得到的余数 p_quotient_reverse = (int*)malloc(512*(sizeof(int*))); // 存放逆序排列后的商 b_list = (int*)malloc(512*(sizeof(int*))); // 存放bn的数组 memset(p_quotient,0,512); // 擦净内存 memset(q_remainer,0,512); memset(p_quotient_reverse,0,512); memset(b_list,0,512); f = *F; // 保存F值,以备后续使用 m = *F; n = *e; temp = m % n; printf("m = %d; n = %d; temp = %d ",m,n,temp); i = 0; while(temp != 0) { q_remainer[i] = temp; a = (m-temp)/n; p_quotient[i] = a; i++; m = n; n = temp; temp = m % n; } for(j=0;j<i;j++) { printf("第%d轮商为%d ",(j+1),p_quotient[j]); printf("第%d轮余数为%d ",(j+1),q_remainer[j]); } //商逆序排列 k = i-1; for(j=0;j<i;j++) { p_quotient_reverse[j] = p_quotient[k--]; } printf("逆序后的商序列为: "); for(j=0;j<i;j++) { printf("%d ",p_quotient_reverse[j]); } //计算bn //插入最初的b0 = 1,及b1 = an 即 b1 = p_quotient_reverse[0] b_list[0] = 1; b_list[1] = p_quotient_reverse[0]; printf("b_list[%d]为:%d ",1,b_list[1]); //迭代计算 for(j=0;p_quotient_reverse[j+1] != 0;j++) { b_list[j+2] = b_list[j+1] * p_quotient_reverse[j+1] + b_list[j]; printf("b_list[%d]为:%d ",(j+2),b_list[j+2]); } printf("b_list完整序列值: "); for(j=0;j<i+1;j++) { printf("%d ",b_list[j]); } // 判断商的个数决定密钥为bn(偶数个)还是 F-bn(奇数个) if(i%2 == 0) { printf("偶数 "); printf("%d ",j-1); printf("%d ",b_list[j-1]); D = b_list[j-1]; } else { printf("奇数 "); printf("%d ",j-1); printf("%d ",b_list[j-1]); printf("%d ",f); D = f - b_list[j-1]; } free(p_quotient); free(q_remainer); free(p_quotient_reverse); printf("%d ",D); printf("返回密钥... "); return D; } int main() { int p, q, e, d, n, fai_n; printf("请输入p、q、e值,用空格间隔开 "); scanf("%d%d%d", &p, &q, &e); //从键盘获取p、q、e值 n = p*q; printf("N = %d ",n); fai_n = (p-1)*(q-1); //Φ(n) printf("φ(n) = %d ",fai_n); getchar(); printf("计算密钥... "); d = _E_Product(&e,&fai_n); printf("密钥计算完成... "); printf("密钥D = %d ",d); getchar(); }

后记

由维基百科描述:
计算e对于φ(n)的模反元素d,所谓"模反元素"就是指有一个整数d,可以使得ed被φ(n)除的余数为1。
ed ≡ 1 (mod φ(n))
这个式子等价于
ed - 1 = kφ(n)
那么选定e后,是否可以利用凑数法去凑出来等式:ed - 1 = kφ(n) 的解?找到k,即
for k from 0 increase,judge [(kφ(n) + 1) % e ] == 0 是否成立,当它成立的时候,就找到了k,然后通过
(kφ(n)+1)% e 得到模逆元d,这个与通过辗转相除法求模逆元好理解的多。
但是对于选定了e之后,等式ed - 1 = kφ(n) 的k解是否是唯一的? 若是不是唯一的,这个方法就出现了漏洞,他仅仅是找到第一个使式子成立的k就结束了。但是反过来讲,若k不唯一,那么d也将是不唯一的,这样会出现对于一个公钥e,私钥d是不唯一的???虽然我没有仔细去研究RSA算法的证明,但我觉得对于一个既定公钥e,与之对应的私钥d必定要是唯一的~~~欢迎补充证明 >_<
n = p*q; fai_n = (p-1)*(q-1); //Φ(n) for (k = 0; (k*fai_n + 1) % e != 0; k++); if ((k*fai_n + 1) % e == 0) d = (k*fai_n + 1) / e;
算数基本定理:任何大于1的整数都可以分解成素数乘积的形式,并且,如果不计分解式中素数的次序,该分解式是唯一的[微软中国1]。
由算数基本定理可知,整数分解为素数乘积的形式唯一,那么可以不用使用辗转相除法求密钥D了!!!