浅谈ACM竞赛中的逆元

2019-04-13 13:32发布

/* Name:浅谈ACM竞赛中的逆元 Copyright:  ecjtu_acm
Author:  yimao
Date:  24-12-10 14:42
Description:  ACM竞赛_数论_逆元 */ 一、百度百科里的定义 密码学中的逆元,也就是我在OJ里做题时要用到的逆元。 设m为正整数,a为正整数,如果存在a' 使得:   a X a' = 1(mod m   成立,则a叫模m的可逆元,a' 叫a模m的逆元。当a与m互素的情况下,即(a,m)=1,则a的模m的逆元总是存在,而且可以用欧几里得除法(欧几里德扩展算法)求得。   逆元在密码学中有广泛应用,AES密码体系的字节替代就是运用了逆元。           二、这是从百度知道里的一个问题及解答: 问题:   也就是如果只知道143和7这两个数,怎么求得5是143(mod7)的乘法逆元素.
我资料上写的是用欧拉公式得出来的,怎么得出来的?
谢谢。懂了再加分~~~~~~~~~
    最佳答案: 143=3mod7 3*5=15=1mod7 1/143mod7=7n+1/13*11mod7 n=3 ,7n+1=22 22/11*13mod7 2/13mod7即7n+2/13 n=9时7n+2=65 65/13=5mod7 11*13mod7 4*6mod7 24mod7 3mod7 三、网上搜来的一份很好的资料
http://www.pediy.com/bbshtml/BBS6/pediy50391.htm
标 题:大家看看这个东西怎么解密啊!!!! (597字)
发信人:blueboy
时 间:2003-1-24 9:26:40
详细信息:
用A1 B1 C1 D1 对M1,M2,M3,M4 加密
  A2 B2 C2 D2
  A3 B3 C3 D3
算法
  (M1 xor A3 xor  0)*A2 mod A1=N1  N1 and FFFF=S1
  (M2 xor B3 xor S1)*B2 mod B1=N2  N2 and FFFF=S2
  (M3 xor C3 xor S2)*C2 mod C1=N3  N3 and FFFF=S3
  (M4 xor D3 xor S3)*D3 mod D1=N4  N4 and FFFF=S4

最后生成的明文为N1,N2,N3,N4

现在已知N1,N2,N3,N4, A1,B1,....C3,D3
知道M1,M2,M3,M4为WORD类型,其他的为整数类型

问应该怎么对N1,N2,N3,N4进行解密操作

现在我的考虑是这个数据不能直接的解密,可能解密还应
该有一个解密的密码表,但是解密的密码表应该可以用加
密的密码表算出来,不知道我说的对不对,各位大侠帮小
弟看看,谢谢了,
标 题:[整理]重新整理答案,修正表格错位问题 (2千字)
发信人:zmworm
时 间:2003-1-24 23:00:04
详细信息:
关于一个解密算法的解答

作者  :  zmworm
E-Mail:  zmworm@sohu.com
HomePage: ZMWorm.Yeah.Net



blueboy问如下问题:

用A1 B1 C1 D1 对M1,M2,M3,M4 加密
  A2 B2 C2 D2
  A3 B3 C3 D3
算法
  (M1 xor A3 xor  0)*A2 mod A1=N1  N1 and FFFF=S1
  (M2 xor B3 xor S1)*B2 mod B1=N2  N2 and FFFF=S2
  (M3 xor C3 xor S2)*C2 mod C1=N3  N3 and FFFF=S3
  (M4 xor D3 xor S3)*D2 mod D1=N4  N4 and FFFF=S4

最后生成的明文为N1,N2,N3,N4

现在已知N1,N2,N3,N4, A1,B1,....C3,D3
知道M1,M2,M3,M4为WORD类型,其他的为整数类型

问应该怎么对N1,N2,N3,N4进行解密操作

现在我的考虑是这个数据不能直接的解密,可能解密还应
该有一个解密的密码表,但是解密的密码表应该可以用加
密的密码表算出来,不知道我说的对不对,各位大侠帮小
弟看看,谢谢了,

答案如下:

因为是字长是WORD,所以
N1=S1
N2=S2
N3=S3
N4=S4

所以加密变换化简为[a]
(M1 xor A3 xor  0)*A2 mod A1=N1
(M2 xor B3 xor N1)*B2 mod B1=N2
(M3 xor C3 xor N2)*C2 mod C1=N3 
(M4 xor D3 xor N3)*D2 mod D1=N4


K1=(M1 xor A3 xor  0)
K2=(M2 xor B3 xor N1)
K3=(M3 xor C3 xor N2)
K4=(M4 xor D3 xor N3)


加密变换化简为[b]
K1*A2 mod A1=N1
K2*B2 mod B1=N2
K3*C2 mod C1=N3 
K4*D3 mod D1=N4

只要我们能求出Ki,Mi也就可求了 因为
M1=(K1 xor A3 xor  0)
M2=(K2 xor B3 xor N1)
M3=(K3 xor C3 xor N2)
M4=(K4 xor D3 xor N3)

所以问题的关键是求 Ki 注意到[b]中每一等式中只有Ki未知,其他量都已知。不妨设

K*e mod f = d (e,f,d为已知量)[c]

设e'为 e 关于f的乘法逆元
(什么是乘法逆元?若e'满足e*e' mod f =1 则称e'为 e 关于f的乘法逆元)
则有
e'*e mod f= 1
根据模运算性质有
d*(e'*e) mod f=d*1=d    [d]

对比 [c] [d] 不难发现
K=d*e' mod f

所以问题转为求e的乘法逆元e'
用扩展的欧几里德算法 可以求e' .算法描述如下
ExtendedEuclid(e,f)
1 (X1,X2,X3):=(1,0,f)
2  (Y1,Y2,Y3):=(0,1,e)
3  if (Y3=0) then return  e'=null//无逆元
4  if (Y3=1) then return  e'=Y2  //Y2为逆元
5  Q:=X3 div Y3
6  (T1,T2,T3):=(X1-Q*Y1,X2-Q*Y2,X3-Q*Y3)
7 (X1,X2,X3):=(Y1,Y2,Y3)
8  (Y1,Y2,Y3):=(T1,T2,T3)
9  goto 3

看不明白算法?我们举个例子:求7关于96的乘法逆元。
 
扩展辗转相除法图示


-41 mod 96 =55 所以55就是7关于96的逆元。
让我们检验一下55*7 mod 96 =1

最后我们取求K的例子,K*7 mod 96 = 13 求K
因为7的乘法逆元是55 所以  K=13*55 mod 96=715 mod 96=43  K=43
检验 43*7 mod 96=288 mod 96 =13

总结解密算法:
K1=:A2'*N1 mod A1
K2=:B2'*N2 mod B1
K3=:C2'*N3 mod C1 
K4=:D2'*N4 mod D1

M1=(K1 xor A3 xor  0)
M2=(K2 xor B3 xor N1)
M3=(K3 xor C3 xor N2)
M4=(K4 xor D3 xor N3)

小结:通过这道问题的解答,我们学习到一些新的知识,知道了什么是乘法逆元,乘法逆元在密码学中的作用也重要,RSA算法就用到了乘法逆元,感兴趣的话,你可以参考RSA方面的书籍。祝你学习愉快!!
标 题:关于此问题的补充,如果乘法逆元不存在的情况如何解密 (1千字)
发信人:zmworm
时 间:2003-1-25 9:13:42
详细信息:
关于一个解密算法的解答(补充)

作者  :  zmworm
E-Mail:  zmworm@sohu.com
HomePage: ZMWorm.Yeah.Net

    刚才说的情况是 e'存在的情况,若e'不存在,应该怎样解密呢?

    首先,我们要知道e满足什么条件时,e'存在。我们有以下定理:

        如果gcd(e,f)=1(即 e,f 互素),那么e有一个模f的乘法逆元。
        [gcd(e,f)=p,表示e,f的最大公约数是p,求最大公约数可以用辗转相除法]

    如果gcd(e,f)=p(p>1) 则 不存在e关于f的乘法逆元。


    现在我们就求乘法逆元不存在时 K*e mod f=d 的解-----------------[e]

        因为 gcd(e,f)=p 所以 p|e, p|f,设 e"=e/p ,f"=f/p ,m=K*e div f,则
        K*e mod f=d => K*e=m*f+d => K*e"*p=m*f"*p+d => d=K*e"*p-m*f"*p=(K*e"-m*f")*p

        所以 p|d, 令 d"=d/p ,则
        K*e mod f=d => K*e"*p=m*f"*p+d"*p => K*e"=m*f"+d" => K*e" mod f"=d"

        而 gcd(e",f")=1,这样我们就可以求e"的逆元e'
        所以 d"*(e'*e") mod f"=d" =>d"*e'*e"*p mod f"*p=d"p
        即 (d"*e')*e mod f=d -------------------------------------[f]

        对比[e] [f] 有 K=d"*e'


        注意 这只是K的一个解
        事实上,Ki=d"*e'+(i-1)f"  (i=1..p) 都满足条件, 因为 (d"*e'+if")*e" mod f"=d"

        也就是说,若gcd(e,f)=p 则K有p个值

    [例] 求 满足K*14 mod 96 =12中K的值

    解 因为gcd(14,96)=2,所以k 有两个解
    e"=14/2=7 f"=96/2=48 d"=12/2=6
    7关于 48的逆元e'=7 (因为 7*7 mod 48 =1)
    所以 Ki=d"*e'+(i-1)f"=6*7+(i-1)*48 (i=1,2)
    解得 K1=42 K2=90

若不存在逆元的解密算法为

K1=:A2'*N1" mod A1
K2=:B2'*N2" mod B1
K3=:C2'*N3" mod C1 
K4=:D2'*N4" mod D1

M1=(K1 xor A3 xor  0)
M2=(K2 xor B3 xor N1)
M3=(K3 xor C3 xor N2)
M4=(K4 xor D3 xor N3)
标 题:对K的补充说明 (695字)
发信人:zmworm
时 间:2003-1-25 11:24:06
详细信息:
关于一个解密算法的解答(对K的补充说明)

作者  :  zmworm
E-Mail:  zmworm@sohu.com
HomePage: ZMWorm.Yeah.Net


(1)若不存在逆元,求K时
    Ki=d"*e'+(i-1)f"
    若 d"*e' 大于 f"时需要进行模运算 即Ki=[(d"*e') mod f"]+(i-1)f"

(2)前面的方法我们已经可以求出至少一组明文,如果您想求出所有满足条件的解,你还要继续往下看。

    细心的您一定发现了我们前面所求得K都是小于f的,而事实上
    若K满足K*e mod f=d ,则所有的Ki=K+i*f(i=1..n) 也满足Ki*e mod f=d
    那么说满足K*e mod f=d的 K应该有无数多个。

    在数学中的确如此,
    在计算机中则不同,要根据字长设字长为n,对每一个K
    应该有 2^n div f 或(2^n div f)+1个
    只要Ki=K+i*f <2^n 都满足
    Ki=K+i*f >2^n 就会发生溢出错误了。
标 题:此算法的具体例子 (1千字)
发信人:zmworm
时 间:2003-1-25 11:25:06
详细信息:
关于一个解密算法的解答(此算法的具体例子)

作者  :  zmworm
E-Mail:  zmworm@sohu.com
HomePage: ZMWorm.Yeah.Net 

[习题]
以下各变量的字长均为8位

用A1=96  B1=96 C1=97 D1=97 
  A2=7  B2=14 C2=21 D2=28
  A3=33  B3=34 C3=35 D3=36
算法 
  (M1 xor A3 xor  0)*A2 mod A1=N1 
  (M2 xor B3 xor N1)*B2 mod B1=N2 
  (M3 xor C3 xor N2)*C2 mod C1=N3
  (M4 xor D3 xor N3)*D2 mod D1=N4
对M1,M2,M3,M4 进行加密操作

求得
  (M1 xor 33 xor  0)*7  mod 96=86
  (M2 xor 34 xor 86)*14 mod 96=80 
  (M3 xor 35 xor 80)*21 mod 97=93
  (M4 xor 36 xor 93)*28 mod 97=25 
即密文为  N1=86 N2=80 N3=93 N4=25

问所有可能的明文M1 M2 M3 M4



gcd(7,96)=1 所以K1 有一个解
7模96的乘法逆元为55 (因为 7*55 mod 96=1)
所以K1=55*N1 mod 96 =26
K1所有可能情况是 26 ,26+96=122 ,122+96=218,
M1=26 xor 33 xor 0=59
M1=122 xor 33 xor 0=91
M1=218 xor 33 xor 0=251

M1 的所有可能是 59, 91, 251


gcd(14,96)=2,所以k 有两个解
e"=14/2=7 f"=96/2=48 d"=80/2=40
7关于 48的逆元e'=7 (因为 7*7 mod 48 =1)
所以 K2[i]i=d"*e'+(i-1)f"=[(40*7) mod 48]+(i-1)*48 (i=1,2)
解得 K2[1]=40 K2[2]=88
K2所有可能情况是 40 ,40+96=136 ,136+96=232, 88 88+96=184
M2=40 xor 34 xor 86=92
M2=136 xor 34 xor 86=252
M2=232 xor 34 xor 86=156
M2=88 xor 34 xor 86=44
M2=184 xor 34 xor 86=204

M2的所有可能是 92, 252, 156, 44, 206

gcd(21,97)=1 所以K1 有一个解
模96的乘法逆元为37 (因为 37*21 mod 97=1)
所以K1=37*N3 mod 97 =46
K1所有可能情况是 46 ,46+97=143 ,143+97=240,
M3=46 xor 35 xor 80=93
M3=143 xor 35 xor 80=252
M3=240 xor 35 xor 80=136

M2的所有可能是 93, 252, 136


M4 留为作业 ,自己求。答案不确定可以问我。