SilentSpiral

RabinPlus

记得刚刚开密码学的时候, 老师曾经说过有一个全新的研究方向, 即想办法让密文不仅可以正常解密,还可以用假的密钥可以解出带有欺骗性语义的假明文

当时我其实就想到了rabin, 记得它一个密文对应四个明文的有趣性质, 不过当时已经把具体的算法还给教我们信安数学的老师了 , 就把这个有(wu)趣(liao)的方向拖到了寒假才去考虑(￣ε(#￣)☆╰╮o(￣皿￣///)

Rabin加密算法了解一下(๑•̀ㅂ•́) ✧
考虑到最终解出来的x是四个一次同余方程的解:
　　{x ≡ m (mod p), x ≡ m (mod q)}
　　{x ≡ m (mod p), x ≡ -m (mod q)}
　　{x ≡ -m (mod p), x ≡ m (mod q)}
　　{x ≡ -m (mod p), x ≡ -m (mod q)}
可由中国剩余定理解得 :
x ≡ ± [m*q*(q-1(mod p)) ± m*p*(p-1(mod q)) ] (mod pq)
易知当两个m都取正的时候可解出来明文 x ≡ m (mod pq)
　(但实际上你并不知道那两个两个二次剩余各自求出来的是m还是-m)
寄希望于由中国剩余定理得到的解可以通过控制p,q的取值得到自己想要的结果
对着这个式子发了一上午呆无果, 甚至在qq上问高中老师, 得到了明确的另请高明的答复……

然后就放弃了中国剩余定理的方向, 转而回到加密过程: C ≡ M2 (mod pq)
我们的目标是通过控制pq的值, 使得明文M与假明文N共享密文C
此时可以得到 :
　　C ≡ N2 ≡ M2 (mod pq)
　　N2 ≡ M2 (mod pq)
　　N2 - M2 ≡ 0 (mod pq)
　　(N+M)*(N-M) ≡ 0 (mod pq)
易知, 该构造要求pq为(N2 - M2 )的因数, 且必须符合模4余3的要求
其中(N2 - M2 )可以天然分解为(N+M)*(N-M)
只需要分别分解(N+M)和(N-M)即可, 找到最大的两个模4余3的素因子, 若二者乘积大于M和N, 则可令p,q 等于这两个因子, 构造成功

出于这个思路, 我特地做了一些尝试, 并且取得了一点点可用以把玩的成果

先说一下我字符串是如何处理成大整数的, 为了节约空间, 使用了GBK编码, 也没有考虑大端序小端序什么的, 感谢python爸爸原生支持大整数_(:з」∠)_

字符串 -> 大整数

1
2
3
str="苟利国家生死以生死以"
bstr=str.encode("gbk")
M=int("".join(["%02x"%i for i in bstr]),16)

大整数 -> 字符串

1
2
3
4
M=3766725027693684650906199485633236
s=hex(M)[2:]       #其实严格来说这里不严谨的, 但我就不告诉你为什么, 略略略
btxt=bytes([int(s[i:i+2],16) for i in range(0,len(s),2)])
txt=btxt.decode("gbk")

构造:

过程:

M = 3766725027693684650906199485633236 (对应明文: 苟…)
N = 4035076373988713014518334522644142 (对应明文: 岂…)
M+N = 7801801401682397665424534008277378
M-N = 268351346295028363612135037010906

而后对两个大整数都进行了千万以内的试除
M-N = 4606573733907171415046778539*73*19*7*3*2
幸运的是 4606573733907171415046778539 通过了Miller-Rabin素性检测, 且符合模4余3的要求
M+N = 169604378297443427509229000179943*23*2
而169604378297443427509229000179943未通过Miller-Rabin素性检测, 对其毫无办法
第二天在某国科大巨佬的帮助下, 在Mathematica上查到了这个大整数的分解结果
ans = 662654996111*1992383443*128462585491
人品爆棚的是这三个质因数都符合模4余3的要求
于是可以开始构造了:

结果:

明文编码: gbk
p=662654996111
q=4606573733907171415046778539
n=p*q=3052569099727291422872833399644123261829
(密文)C=2413667364007742399945425196351299817253

解出的四个明文:
M1=3052565333002263729188182493444637628593 (解码失败)
M2=3052565064650917434159818881309600617687 (解出乱码)
M3=4035076373988713014518334522644142 (gbk: 岂因祸福避趋之)
M4=3766725027693684650906199485633236 (gbk: 苟利国家生死以)

可以看到事实上这个构造已经很费力了, 于个人觉得这个构造法只能用于把玩, 实际应用价值极其有限, 就算只对明文最关键的部分进行语义欺骗, 利用它生成的pq加密全文, 其生成pq的成本也是难以接受的, 毕竟, 如果这么随随便便就让你把大整数分解成功的话….

……那我RSA的面子往哪放? 你Rabin自己的面子往哪放?

最后附一下我写的风格被大佬日常黑成狗的解密代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def powmod(m,e,n):  
	c=1
	e=bin(e)[2:]
	k=len(e)
	for i in range(k):
		c = c**2 % n
		if e[i]=='1':
			c=c*m %n
	return(c)
	
def egcd(a,b):
	if a==0:
		return (b,0,1)
	else:
		g,y,x=egcd(b%a,a)  # g为公因子
		return (g,x-(b//a)*y,y)
		
def modinv(a,m):
	g,x,y = egcd(a,m)
	if (g!=1):
		print('modular inverse does not exist')
	else:
		return x%m

def main():
	p=eval(input('请输入私钥p:'))
	q=eval(input('请输入私钥q:'))
	n=p*q
	c=eval(input('请输入密文:'))
	a1=powmod(c,(p+1)//4,n)
	a2=p-a1
	b1=powmod(c,(q+1)//4,n)
	b2=q-b1
	
	M=[]
	M.append((b1*p*modinv(p, q)+a1*q*modinv(q, p))%n)
	M.append((b1*p*modinv(p, q)+a2*q*modinv(q, p))%n)
	M.append((b2*p*modinv(p, q)+a1*q*modinv(q, p))%n)
	M.append((b2*p*modinv(p, q)+a2*q*modinv(q, p))%n)
	
	for i in M:
		print(i)
		s=hex(i)[2:]
		plaintext = bytes([int(s[j:j+2],16) for j in range(0,len(s),2)])
		try:
			print(" gbk:"+plaintext.decode('gbk'))
		except:
			print("f**k,解码失败")
	return 0

if __name__ == "__main__":	
	main()	
	input("请按关机键继续...")

消灭PEP8暴政! 世界属于Tab!

打赏