A new cryptosystem based on Lucas functions

基于一道CTF题目，也就是如下。

import random
from Crypto.Util.number import isPrime

m, Q = """REDACTED""", 1

def genPrimes(size):
    base = random.getrandbits(size // 2) << size // 2
    base = base | (1 << 1023) | (1 << 1022) | 1
    while True:
        temp = base | random.getrandbits(size // 4)
        if isPrime(temp):
            p = temp
            break
    while True:
        temp = base | random.getrandbits(size // 4)
        if isPrime(temp):
            q = temp
            break
    return (p, q)

def pow(m, e, n):
    return v(e)

def v(n):
    if n == 0:
        return 2
    if n == 1:
        return m
    return (m*v(n-1) - Q*v(n-2)) % N

p, q = genPrimes(1024)

N = p * q
e = 0x10001

print("N:", N)
print("c:", pow(m, e, N))

"""
N: 18378141703504870053256589621469911325593449136456168833252297256858537217774550712713558376586907139191035169090694633962713086351032581652760861668116820553602617805166170038411635411122411322217633088733925562474573155702958062785336418656834129389796123636312497589092777440651253803216182746548802100609496930688436148522617770670087143010376380205698834648595913982981670535389045333406092868158446779681106756879563374434867509327405933798082589697167457848396375382835193219251999626538126258606572805220878283429607438382521692951006432650132816122705167004219371235964716616826653226062550260270958038670427
c: 14470740653145070679700019966554818534890999807830802232451906444910279478539396448114592242906623394239703347815141824698585119347592990685923384931479024856262941313458084648914561375377956072245149926143782368239175037299219241806241533201175001088200209202522586119648246842120571566051381821899459346757935757111233323915022287370687524912870425787594648397524189694991735372527387329346198018567010117587531474035014342584491831714256980975368294579192077738910916486139823489975038981139084864837358039928972730135031064241393391678984872799573965150169368237298603189344477806873779325227557835790957023000991
"""

我们先来了解一下Lucas序列吧。

Lucas序列就像广义的Fibocacci序列, 形式如下
\begin{equation}
V{k+1}(P, Q) = PV_k(P, Q) - QV{k-1}(P, Q), \ V_1(P, Q) = P, \ V_0(P, Q) = 2
\end{equation}

对于我们密码的应用，我们只需要计算序列\((V_n(P, 1))\).

因为我们知道很多Fibonacci序列的性质，除了通项公式

$$F(n) = \frac{\lambda_1^n - \lambda_2^n}{\lambda_1 - \lambda_2} \ as\ \lambda_1\ and\ \lambda_2\ are\ eigenvalues$$

还有一些幂的性质，可以见一些数学杂志。我们直接引入Lucas序列中类似的性质：

$$V_{2n} = V_n^2 - 2 $$并且还有 \begin{equation*} V_{2n+1} = V(n)V(n-1) - PQ_{n-1} \end{equation*} 加密过程： 我们用公钥(e, N)来加密，和RSA类似，通过计算 $$ f(P) = V_e(P, 1)\ (mod\ N) \equiv C\ (mod\ N)$$

来得到C,也就是说我们把P取值为明文m即可。

解密过程：

既然有公钥(e, N)， 同样有私钥(d, N), 我们只需要算出

$$f(C) = V_d(C, 1)\ (mod\ N) \equiv V_d(V_e(P, 1), 1) \equiv V_{de}(P, 1) \equiv P\ (mod\ N)$$

也就是得到了明文。

下面写出d的求解方法：

d = gmpy2.invert(e, R)

而R是什么，这里并不是欧拉函数，而是
$R = lcm(p - (\frac{D}{p}), q - (\frac{D}{q}))$
,而中间的括号不只是简单的括起来，而是勒让德符号，也就是判断是否为二次剩余而输出1或-1.

最后拿到明文

解密如下：
import os
import Crypto.Util.number
import gmpy2
import sys
#见论文中的写法。
sys.setrecursionlimit(5000)#python有最大递归限制，可以通过次函数修改限制。
N = 18378141703504870053256589621469911325593449136456168833252297256858537217774550712713558376586907139191035169090694633962713086351032581652760861668116820553602617805166170038411635411122411322217633088733925562474573155702958062785336418656834129389796123636312497589092777440651253803216182746548802100609496930688436148522617770670087143010376380205698834648595913982981670535389045333406092868158446779681106756879563374434867509327405933798082589697167457848396375382835193219251999626538126258606572805220878283429607438382521692951006432650132816122705167004219371235964716616826653226062550260270958038670427
c = 14470740653145070679700019966554818534890999807830802232451906444910279478539396448114592242906623394239703347815141824698585119347592990685923384931479024856262941313458084648914561375377956072245149926143782368239175037299219241806241533201175001088200209202522586119648246842120571566051381821899459346757935757111233323915022287370687524912870425787594648397524189694991735372527387329346198018567010117587531474035014342584491831714256980975368294579192077738910916486139823489975038981139084864837358039928972730135031064241393391678984872799573965150169368237298603189344477806873779325227557835790957023000991
e = 0x10001;
m = c  # 用于给卢卡斯序列的m赋值。
p = 135566004969921829046861317679102794894163252891621004552763069255612086965641424719754859767153782381891044077537624735662301899417143962916558791489710971298124937969427903581890089403413545652984524659790357002447801666607195021452029447206533810446315939039775701027454771450154054624400219767469987538497
q = 135566004969921829046861317679102794894163252891621004552763069255612086965641424719754859767153782381891044077537624735662301899417143962916558791489710971298124937969427903581890089403413545652984524659790357002447801666607195021441224446867180097273643121640903324702747770969633717818870639347019154977691
# 先分解得到p, q

D = c ** 2 - 4;
LS_p = gmpy2.legendre(D, p);
LS_q = gmpy2.legendre(D, q);
R = gmpy2.lcm(p - LS_p, q - LS_q);
d = gmpy2.invert(e, R);

v_dict = {}


def v(n):
    if n == 0:
        return 2;
    if n == 1:
        return m;
    if n in v_dict.keys():
        return v_dict[n];
    if n % 2 == 0:
        ret = (pow(v(n // 2), 2, N) - 2) % N
    else:
        ret = (m * pow(v(n // 2), 2, N) - 1 * v(n // 2) * v(n // 2 - 1) - m * pow(1, n, N)) % N;
        #ret = (v(n//2) * v(n//2 - 1) - m * 1) % N不知道为什么这个跑不通。
    v_dict[n] = ret
    return ret


flag = v(d);
print(Crypto.Util.number.long_to_bytes(flag))

我们可以看到ret的两个输出就是刚才我们介绍的Lucas序列的两个性质，分别为奇数和偶数项的快速算法，可自己求证。

部分引用于https://www.sebven.com/ctf/2021/03/01/UMassCTF-Weird-RSA.html