DjangoBB LoFi version

Полная версия: RSA шифрование. Непонятное поведение оператора %

Начало » Python для экспертов » RSA шифрование. Непонятное поведение оператора %

kozlo22

Ноя. 11, 2014 00:08:36

Пишу скрипт для RSA-шифрования.

def elier_func(p, q):
	'''Вычислеяет функцию Эйлера'''
	return p*q - p - q + 1
def secret_exp(e, qn): # qn - результат функции Ейлера
	'''Вычисляет секретную экспоненту'''
	print(e, qn)
	return pow(e,-1) % qn
def enc(p, q, e, text):
	'''Шифррует строку переданную в праметре text'''
	n = p * q
	eiler_func_res = elier_func(p ,q) #q(n)
	#print('{ {0}, {1} }'.format(elier_func, n))
	res = []
	if text.isalpha():
		for i in text:
			if i.isalpha():
				symb_to_enc = ord(i)
			else:
				symb_to_enc = i
		print('{} ** {} % {}'.format(symb_to_enc, e, n))
		c = (int(symb_to_enc) ** e) % n
		res.append(c)
	elif text.isdigit():
		res = (pow(int(text), e)) % n 
	return res
def descr(p, q, e, text):
	'''Расшифровывает строку переданную в праметре text'''
	n = p * q
	sec_exp = secret_exp(e, elier_func(p, q)) # d
	print(sec_exp)
	res = []
	if type(text) == type([]):
		for i in text:
			symb_to_desc = (int(i) ** int(sec_exp)) % n
			print('{} ** {} % {} = {}'.format(i, int(sec_exp), n, symb_to_desc))
			res.append(symb_to_desc)
	else:
		res = (pow(int(text), e)) % n
		print('{} ** {} % {}'.format(text, sec_exp, n))
	return res
def main():
	p = input('Enter first open key >>> ')
	q = input('Enter second open key >>> ')
	e = input('Enter exponent >>> ')
	text_to_enc = input('Enter any text to encrypt >>> ') # m
	try:
		p, q, e = int(p), int(q), int(e)
	except ValueError:
		pass
	encrypted_text = enc(p, q, e, text_to_enc)
	desctypted_text = descr(p , q, e, encrypted_text)
	return(encrypted_text, desctypted_text)
print(main())

Беру пример из wiki
Шифрует верно, расшифровать не может. Как я понял: опертор % возвращает значение делимого. Т.е. вычисление секретной экспоненты происходит в функции secret_exp, получается при значениее експоненты 3, должно быть следующее выражение 0.33333333 % 9167368 - возвращает 0.33333333.
Что я делаю не так?

Up
Нашел способ при котором что-то меняется - использовать функцию Decimal из модуля decimal.
Но все равно результат неверный. Сейчас при тех же значениях значение секретной экспоненты равно 0.3333333333333333148296162562

terabayt

Ноя. 11, 2014 00:36:14

rsa
и документация

terabayt

Ноя. 11, 2014 15:48:22

ахах, снижать репутацию из-за того что кто-то пытается помочь?! ну, ну…..

kozlo22

Ноя. 11, 2014 15:59:16

terabayt
ахах, снижать репутацию из-за того что кто-то пытается помочь?! ну, ну…..

Бесполезная помощь. Я задал вопрос “Что я делаю не так?”. Вы же даете ссылки на ресурсы с готовым решением, которые не дают ответа на мой вопрос. Да и если бы было нужно готовое решение, я не стал бы велосипедить.

terabayt

Ноя. 11, 2014 16:30:38

res = (pow(int(text), e)) % n

замените на

res = (pow(int(text), sec_exp)) % n

kozlo22

Ноя. 11, 2014 16:50:41

terabayt
ничего не имзенилось :\

terabayt

Ноя. 11, 2014 16:54:17

а вместо

def secret_exp(e, qn): # qn - результат функции Ейлера
	'''Вычисляет секретную экспоненту'''
	print(e, qn)
	return pow(e,-1) % qn

def extended_gcd(a, b):
    x = 0
    y = 1
    lx = 1
    ly = 0
    oa = a
    ob = b
    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 (ly < 0): ly += oa
    return lx
def secret_exp(e, p, q): 
    phi_n = (p - 1) * (q - 1)
    d = extended_gcd(e, phi_n)
    print('e - ', e, d)
    return d

и замените

sec_exp = secret_exp(e, elier_func(p, q))

на

sec_exp = secret_exp(e, p, q)

terabayt

Ноя. 11, 2014 16:56:14

вот весь код, только я там малек переделал, убрал инпуты и еще что-то

def elier_func(p, q):
    return p*q - p - q + 1
def extended_gcd(a, b):
    x = 0
    y = 1
    lx = 1
    ly = 0
    oa = a
    ob = b
    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 (ly < 0): ly += oa
    return lx
def secret_exp(e, p, q): 
    phi_n = (p - 1) * (q - 1)
    d = extended_gcd(e, phi_n)
    print('e - ', e, d)
    return d
def enc(p, q, e, text):
    n = p * q
    eiler_func_res = elier_func(p ,q) #q(n)
    #print('{ {0}, {1} }'.format(elier_func, n))
    res = []
    if text.isalpha():
        for i in text:
            if i.isalpha():
                symb_to_enc = ord(i)
            else:
                symb_to_enc = i
        print('{} ** {} % {}'.format(symb_to_enc, e, n))
        c = (int(symb_to_enc) ** e) % n
        res.append(c)
    elif text.isdigit():
        res = (pow(int(text), e)) % n
    return res
def descr(p, q, e, text):
    n = p * q
    sec_exp = secret_exp(e, p, q) # d
    res = []
    if type(text) == type([]):
        for i in text:
            symb_to_desc = (int(i) ** int(sec_exp)) % n
            print('{} ** {} % {} = {}'.format(i, int(sec_exp), n, symb_to_desc))
            res.append(symb_to_desc)
    else:
        res = (pow(int(text), sec_exp)) % n#!!!
        print('{} ** {} % {}'.format(text, sec_exp, n))
    return res
def main():
    p = 3557
    q = 2579
    e = 3
    text_to_enc = '111111'
    try:
        p, q, e = int(p), int(q), int(e)
    except ValueError:
        pass
    encrypted_text = enc(p, q, e, text_to_enc)
    desctypted_text = descr(p , q, e, encrypted_text)
    return(encrypted_text, desctypted_text)
print(main())

kozlo22

Ноя. 17, 2014 20:03:50

В общем, как я понял: операция деления по модулю не используется при автоматизации процесса шифрования алгоритмом RSA. Для вычисления d (наибольшего общего делителя) используется расширенный алгоритм Евклида.

Уже есть реализации этого алгоритма, но почему-то при тупом ctrl+c - ctrl+v ответ не сходится. Разбираться уже лень. Решил не заморачиваться и использовать готовое решение (i.e. модуль rsa, который посоветовал terabayt)

Вот на чем я остановился:

from decimal import Decimal
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
def modinv(a, m):
    gcd, x, y = egcd(a, m)
    if gcd != 1:
        return None  # modular inverse does not exist
    else:
        return x % m
def secret_exp(e, qn): # qn - результат функции Ейлера
	'''Вычисляет секретную экспоненту'''
	return Decimal(pow(e,-1)) % Decimal(qn)
def enc(p, q, e, text):
	'''Шифррует строку переданную в праметре text'''
	n = p * q
	eiler_func_res = (p-1)*(q-1) #q(n)
	print('q(n) = {0}, n = {1}'.format(eiler_func_res, n))
	res = []
	if text.isalpha():
		for i in text:
			if i.isalpha():
				symb_to_enc = ord(i)
			else:
				symb_to_enc = i
		print('{} ** {} % {}'.format(symb_to_enc, e, n))
		c = (int(symb_to_enc) ** e) % n
		res.append(c)
	elif text.isdigit():
		res = (pow(int(text), e)) % n 
	return res
def descr(p, q, e, text):
	'''Расшифровывает строку переданную в праметре text'''
	n = p * q
	sec_exp = modinv(e, ((p-1)*(q-1))) # d
	print(sec_exp)
	res = []
	if type(text) == type([]):
		for i in text:
			symb_to_desc = (int(i) ** int(sec_exp)) % n
			res.append(symb_to_desc)
	else:
		res = modinv(pow(int(text), sec_exp))
		
	return res
def main():
	p = input('Enter first open key >>> ')
	q = input('Enter second open key >>> ')
	e = input('Enter exponent >>> ')
	text_to_enc = input('Enter any text to encrypt >>> ') # m
	try:
		p, q, e = int(p), int(q), int(e)
	except ValueError:
		pass
	encrypted_text = enc(p, q, e, text_to_enc)
	desctypted_text = descr(p , q, e, encrypted_text)
	return(encrypted_text, desctypted_text)
print(main())