Как реализовать алгоритм RSA на Python?

Question

[Tolik]

Собственно, хочу собственную независимую либу для шифровки сделать. Я так понял, питону не нужны никакие дополнительные библиотеки для работы с огромными числами. Это хорошо.

Но завис я на вычислении секретной экспоненты. Делал как здесь на примере (примерно посредине страницы).

Мой вариант:d = (e ** -1) % f но он делает совсем не то, что надо (брал такие же циферки)

Answer 1

[Михаил Алексеев]

Подсмотрите как здесь реализовали
code.activestate.com/recipes/578838-rsa-a-simple-a...

Библиотека:
https://pypi.python.org/pypi/rsa

Comments

[Tolik]

def extended_gcd(a, b):
    '''Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb
    '''
    # r = gcd(a,b) i = multiplicitive inverse of a mod b
    #      or      j = multiplicitive inverse of b mod a
    # Neg return values for i or j are made positive mod b or a respectively
    # Iterateive Version is faster and uses much less stack space
    x = 0
    y = 1
    lx = 1
    ly = 0
    oa = a                             #Remember original a/b to remove 
    ob = b                             #negative values from return results
    while b != 0:
        q = a // b
        (a, b)  = (b, a % b)
        (x, lx) = ((lx - (q * x)),x)
        (y, ly) = ((ly - (q * y)),y)
    if (lx < 0): lx += ob              #If neg wrap modulo orignal b
    if (ly < 0): ly += oa              #If neg wrap modulo orignal a
    return (a, lx, ly)                 #Return only positive values


def inverse(x, n):
    '''Returns x^-1 (mod n)

    >>> inverse(7, 4)
    3
    >>> (inverse(143, 4) * 143) % 4
    1
    '''

    (divider, inv, _) = extended_gcd(x, n)

    if divider != 1:
        raise ValueError("x (%d) and n (%d) are not relatively prime" % (x, n))

    return inv

спасибо, нашел

Answer 2

[Николай]

F = (P - 1) * (Q - 1)
print "Вычисляем функцию Эйлера F(n)=(p-1)*(Q-1)"
print "F =",F

# Use first simple number.
Ko = 0
i = 2
while i < F:
	e = Euclid(F, i)
	if e == 1:
		Ko = i;
		break;
	i += 1

print "Выбираем значение открытого ключа Кo с соблюдением условий"
print "1<Кo<F(n), Кo и F(n) – взаимно простые числа (их НОД=1)"
print "Ko =",Ko

i = 2
while i < n:
	if (i * Ko) % F == 1:
		Kc = i
		break
	i += 1

print "Находим Kc =",Kc

C = M**Ko % n
print "Шифрование: C =",C

Md = C**Kc % n
print "Расшифрование: M =",Md

Answer 3

[Максим Васильев]

Рекомендация от профессора стэндфордского университета Dan Bioneh на курсе крипторгафии:
не пытайтесь реализовать алгоритмы сами!

Comments

[koi com]

хах. ты это преподу моему скажи)