(RSA) Этот скрипт, который я получил из stackoverflow, возвращает отрицательное значение d - PullRequest
Новая
       8

(RSA) Этот скрипт, который я получил из stackoverflow, возвращает отрицательное значение d

0 голосов
/ 07 октября 2018

Итак, я наткнулся на этот поток здесь с этим сценарием, и он возвращает отрицательное значение d, а мои значения p и q являются простыми.Есть причина для этого?Возможно просто неисправный скрипт? 

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        gcd = b
    return gcd, x, y

def main():

    p = 153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433
    q = 156408916769576372285319235535320446340733908943564048157238512311891352879208957302116527435165097143521156600690562005797819820759620198602417583539668686152735534648541252847927334505648478214810780526425005943955838623325525300844493280040860604499838598837599791480284496210333200247148213274376422459183
    e = 65537
    ct = 313988037963374298820978547334691775209030794488153797919908078268748481143989264914905339615142922814128844328634563572589348152033399603422391976806881268233227257794938078078328711322137471700521343697410517378556947578179313088971194144321604618116160929667545497531855177496472117286033893354292910116962836092382600437895778451279347150269487601855438439995904578842465409043702035314087803621608887259671021452664437398875243519136039772309162874333619819693154364159330510837267059503793075233800618970190874388025990206963764588045741047395830966876247164745591863323438401959588889139372816750244127256609

    # compute n
    n = p * q

    # Compute phi(n)
    phi = (p - 1) * (q - 1)

    # Compute modular inverse of e
    gcd, a, b = egcd(e, phi)
    d = a

    print( "n:  " + str(d) );

    # Decrypt ciphertext
    pt = pow(ct,d,n)
    print( "pt: " + str(pt) )

if __name__ == "__main__":
    main()

1 Ответ

0 голосов
/ 07 октября 2018

Это может произойти, я объясню почему ниже, но для практических целей вы захотите узнать, как это исправить.Ответ заключается в том, чтобы добавить phi к d и использовать это значение вместо этого: все будет работать так, как должно RSA.

Так почему же это происходит?Алгоритм вычисляет расширенный gcd.Результат egcd равен a*e + b*phi = gcd, а в случае RSA мы имеем gcd = 1, поэтому a*e + b*phi = 1.

Если вы посмотрите на это уравнение по модулю phi (что является порядком мультипликативногоgroup), затем a*e == 1 mod phi, что необходимо для работы RSA.Фактически, с помощью той же конгруэнции вы можете сложить или вычесть любое кратное от phi до a, и конгруэнция все еще сохраняется.

Теперь рассмотрим уравнение еще раз: a*e + b*phi = 1.Мы знаем, e и phi являются положительными целыми числами.Вы не можете иметь все положительные целые числа в этом уравнении, иначе не получится, что оно сложится в 1 (это будет намного больше 1).Это означает, что либо a, либо b будет отрицательным.Иногда это будет a, что отрицательно, в других случаях это будет b.Когда это b, тогда ваш a получается так, как вы ожидаете: положительное целое число, которое вы затем присваиваете значению d.Но в остальное время вы получаете отрицательное значение для a.Мы не хотим этого, поэтому просто добавьте phi к нему и сделайте его значением d.

...