一字节Patch Lucas公钥算法

BinCrack

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如下：

[C] 纯文本查看 复制代码

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，此时只需要稍加改动，具体实现如下：

[Python] 纯文本查看 复制代码

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

仅用于显示

AC12E8E --> AC12E16
37 30 44 41 43 31 32 45 38 45 --> 37 30 44 41 43 31 32 45 31 36

wincmd.zip (295 Bytes, 下载次数: 24)

2022-2-11 22:07 上传

点击文件名下载附件

wgz001

表哥666，带带我

530812wxh

表哥，求带啊，，，，，，，，，

smallhorse

师傅666，随手就是一发

飞天

表哥神嚓嚓了，膜拜。

哥又回来了

膜拜啊，都成精了。。。

xiaomils

大神 学习了

xingbing

表哥666，膜拜。

bsb888

666. 膜拜大佬