LUC_RSA

https://www.math.u-bordeaux.fr/~gcastagn/publi/crypto_quad.pdf

https://www.researchgate.net/publication/26623030_A_New_Computation_Algorithm_for_a_Cryptosystem_Based_on_Lucas_Functions

最近通过qwb了解到了这个新东西，顺手进一步加深了对于LUCAS序列的理解。

典型例题

UMass CTF 2021 - Weird RSA

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
"""

LUC-RSA Solution

So how does it work? Well to encrypt (as we’ve seen) we calculate the e-th order Lucas sequence with P=m and Q=1. Then, to decrypt we calculate the d-th order Lucas sequence with P=c and Q=1. Huh, sounds quite neat. Our next step is to find the private exponent d, however there’s a catch. We cannot use our familiar

那么它是如何工作的呢？好吧，为了加密（正如我们所看到的），我们计算 P=m 和 Q=1 的第 e 阶卢卡斯序列。然后，为了解密，我们计算 P=c 和 Q=1 的第 d 阶卢卡斯序列。呵呵，听起来很整洁。我们的下一步是找到私有指数 d，但有一个问题。我们不能使用我们熟悉的

d = ~e % phi(N),

instead we use 取而代之的是，我们使用

d = ~e % LCM( (p +- 1), (q +- 1) ).

Now we end up with four possible decryption keys. We could easily try them all out, but we can also find the proper form from

现在我们最终得到了四个可能的解密密钥。我们可以很容易地尝试它们，但我们也可以从中找到合适的形式

d = ~e % LCM( (p - LS(D/p)), (q - LS(D/q)) )

where LS is the Legendre symbol and D = C^2 - 4 the discriminant (abc-formula, anyone?). Finally, just to speed things up, we implement a more efficient encryption function (provided by the chall’s author: Soul). Now we can go and get ourselves a nice flag