一字节Patch Lucas公钥算法
本帖最后由 BinCrack 于 2022-2-12 18:52 编辑bugfix：修复移植时的一处bug，当msg较大时，加密结果错误。（但是在原版Crypto++库中，如果msg足够大，加解密依然会出问题，原因未知）
玩公子最近跟TC过不去，其中的一个核心公钥算法如该贴所示：https://www.chinapyg.com/thread-142517-1-1.html。在回复中了解到是Lucas公钥算法，孤陋寡闻了。在RSA中，当N太大以至于无法分解时，通常一字节patch掉N来构造一组已知的公私钥对。由于该算法与RSA非常相似，本文尝试同样的Patch思路。
1. 寻找可用N
正常情况下N为两个大素数p和q的乘积，我们只需要逐字节修改N，尝试找到一个素数，此时可以认为p和q为别为1和N。随便一找就能得到一大堆备用的N如下：
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93c1fad457a17ca85beb40f3fa9152770dac12e163b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93c1fad457a17ca85beb40f3fa9152770dac12e453b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93c1fad457a17ca85beb40f3fa9152770dac12eb13b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93c1fad457a17ca85beb40f3fa9152770dac12edb3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93c1fad457a17ca85beb40f3fa91527c9dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93c1fad457a17ca85beb40f9ea9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93c1fad457a17ca85beb45c3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93c1fad457a17ca85beb4aa3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93c1fad457a17ca85be140f3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93c1fad457a17ca18beb40f3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93c1fad457a17cabdbeb40f3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93c1fad457a17cadfbeb40f3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93c1fad457ae5ca85beb40f3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93c1fad458517ca85beb40f3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93c1fadc97a17ca85beb40f3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93c1fadd87a17ca85beb40f3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93c28ad457a17ca85beb40f3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93e1fad457a17ca85beb40f3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d9d81fad457a17ca85beb40f3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3bd3c1fad457a17ca85beb40f3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc639312fd93c1fad457a17ca85beb40f3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc639c1c3d93c1fad457a17ca85beb40f3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc639ebc3d93c1fad457a17ca85beb40f3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafd713931c3d93c1fad457a17ca85beb40f3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eac3c63931c3d93c1fad457a17ca85beb40f3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b7251fdc63931c3d93c1fad457a17ca85beb40f3fa9152770dac12e8e3b912d
0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b725ffdc63931c3d93c1fad457a17ca85beb40f3fa9152770dac12e8e3b912d
2. Python实现与验证
Lucas的相关实现代码较少，于是照着Crypto++移植了一份到Python中。需要注意的是，在使用私钥加解密时，原版实现中“欧几里得乘法逆”计算部分会报错。归根结底是p和q取值的锅，导致模数被计算为0，此时只需要稍加改动，具体实现如下：
import gmpy2
def Lucas(e, p, n):
v,v1 = p,(p*p-2)%n
i = len(bin(e))-3
while (i>0):
i-=1
if ((e>>i)&1):
v = (v*v1 - p) % n
v1 = (v1*v1 - 2) % n
else:
v1 = (v*v1 - p) % n
v = (v*v - 2) % n
return v
def Jacobi(aIn, bIn):
a, b = aIn%bIn, bIn
result = 1
while (a > 0):
i=0
while ((a >> i)&1 == 0):
i+=1
a>>=i
if (i%2==1 and (b%8==3 or b%8==5)) ^ (a%4==3 and b%4==3):
result = -result
a,b=b,a
a %= b
return result if(b==1) else 0
def InverseLucas(e, m, p, q, u):
d = (m*m-4)
t1 = p-Jacobi(d,p)
p2 = Lucas(int(gmpy2.invert(e,t1)), m, p)
q2 = Lucas(e, m, q)
return p * (u * (q2-p2) % q) + p2
N=0xaad4474dc8387e81bb095d810f4f4f21d5d7ccc756e3d6e5dee48ac000c25aa0efad0ad3a5ac46f15b50249597461bbb87cdc3f1ba37c17a9a207a3603e38e718f9927a5eb38005d8b72eafdc63931c3d93c1fad457a17ca85beb40f3fa9152770dac12e163b912d
e=0x10001
msg = 0x1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345
enMsg = InverseLucas(e,msg,N,1,0)
print(hex(enMsg))
deMsg = Lucas(e,enMsg,N)
print(hex(deMsg))
本帖最后由 wai1216 于 2022-2-11 22:09 编辑
仅用于显示
AC12E8E --> AC12E16
37 30 44 41 43 31 32 45 38 45 --> 37 30 44 41 43 31 32 45 31 36
表哥666，带带我 表哥，求带啊，，，，，，，，，
师傅666，随手就是一发 表哥神嚓嚓了，膜拜。 膜拜啊，都成精了。。。 大神 学习了 表哥666，膜拜。 666. 膜拜大佬
页:
[1]
2