Уведомления

Группа в Telegram: @pythonsu

#1 Апрель 20, 2010 20:55:54

akolesnikov
От:
Зарегистрирован: 2009-10-26
Сообщения: 36
Репутация: +  0  -
Профиль   Отправить e-mail  

rsa - проблемы с декодированием

Добрый вечер.
Задача - реализовать алгоритм RSA с целью демонстрации работы самого алгоритма. Т.е. никаких извращенств, модуль не будет использоваться в реальных задачах, поэтому стойкости от него не требуется.

Что у меня получилось:

import random,  math,  string

class RSA:
def __init__(self):
self.lets=string.letters+' '
self.strength=2
self.text=''
self.res=[]
self.keys=[]
def fact(self, x):
res=1
for i in range(1,x+1):
res*=i
return res
def is_easy(self, n):
if (self.fact(n-1)+1)%n==0:
return True
else:
return False
def NOD(self, a,b):
while b:
a,b=b,a%b
return a
def findPrimes(self):
self.p=4
self.q=4
while not self.is_easy(self.p):
self.p=random.randint(1*self.strength, 10*self.strength)
while not self.is_easy(self.q):
self.q=random.randint(1*self.strength, 10*self.strength)
self.n=self.p*self.q
self.m=(self.p-1)*(self.q-1)
self.d=4
while abs(self.NOD(self.d, self.m))!=1:
self.d=random.randint(10*self.strength,1000*self.strength)
self.e=0
for self.e in range(99998, 0, -1):
if (self.e*self.d)%self.m==1:
break
def encrypt(self):
self.text=[self.lets.index(n) for n in self.text]
for i in self.text:
self.res.append(int(i)**self.e%self.n)
#print "Open key e=%i n=%i"%(self.e, self.n)
#print "Private key d=%i n=%i"%(self.d, self.n)
#print "Cryptophrase = %s"%(' '.join([str(i) for i in self.res]))
return {'e':self.e, 'd':self.d, 'n':self.n, 'crypto':str(' '.join([str(i) for i in self.res]))}

def decrypt(self):
self.n=self.keys[0][1]
self.d=self.keys[1][0]
for i in self.text.split(' '):
print int(i)**int(self.d)%int(self.n)
self.res+=(self.lets[int(i)**int(self.d)%int(self.n)])
return ''.join([i for i in self.res])

while 1:
my=RSA()
my.text=raw_input('Enter text: ')
started=my.text
my.findPrimes()
result=my.encrypt()

my=RSA()
my.text=result['crypto']
my.keys=[[result['e'], result['n']], [result['d'], result['n']]]
l=my.decrypt()
if l!=started:
print "Started: %s"%started
print "e=%i d=%i n=%i"%(result['e'], result['d'], result['n'])
print "Ended: %s"%l
raw_input()
Уважаемые питонисты, подскажите, где ошибка. Дело в том, что расшифровка часто происходит неверно. Т.е. вызываем метод decrypt(), расшифровывает неправильно. После этого, не изменяя вводные значения, запускаем повторно - и вуаля, все расшифровано верно. Мистика какая-то… В алгоритме вроде проблемы нет, я подозреваю что проблема из-за работы с большими числами, из-за этого где-то косяк. Хотелось бы получить подсказки, в чем проблема и как ее лечить.
Заранее спасибо!



Офлайн

#2 Апрель 20, 2010 21:07:52

akolesnikov
От:
Зарегистрирован: 2009-10-26
Сообщения: 36
Репутация: +  0  -
Профиль   Отправить e-mail  

rsa - проблемы с декодированием

Сразу поясню: вся работа ведется с числами, т.е. введеный текст преобразуется в набор чисел-индексов строки string.letters+' '

В конце программы - бесконечный цикл, это я пытался врубиться, при каких переменных возникает сбой декодирования.

Сам алгоритм описан на википедии и здесь http://pavel.przone.ru/rsa.html, ну а вообще очень много где про него есть.

И еще, просьба не предлагать использовать готовые варианты - по-первых, это часть проекта, а во-вторых, стыдно мне очень, что такой простой алгоритм не работает :rolleyes:



Офлайн

#3 Апрель 20, 2010 21:19:19

Zubchick
От:
Зарегистрирован: 2009-07-08
Сообщения: 613
Репутация: +  0  -
Профиль   Отправить e-mail  

rsa - проблемы с декодированием

сомневаюсь, что тут кто-то будет разбираться. Я писал рц6 тут недавно, три дня дебажил, блин, оказалось что я в одном месте перепутал циклический сдвиг влево с циклическим сдвигом вправо…

Советую научиться пользоваться pdb и попрогонять по шагам код смотря по промежуточным значениям. Так же возьмите простые числа маленькие, в районе первой 20тки и просчитайте на бумажке все шаги. потом запустите в проге.



Офлайн

#4 Апрель 20, 2010 21:35:22

akolesnikov
От:
Зарегистрирован: 2009-10-26
Сообщения: 36
Репутация: +  0  -
Профиль   Отправить e-mail  

rsa - проблемы с декодированием

спасибо за наводку - pdb отличная вещь. сейчас буду правда работать с маленькими числами и проверять.



Офлайн

#5 Апрель 21, 2010 20:10:19

Viper
От:
Зарегистрирован: 2006-11-08
Сообщения: 137
Репутация: +  0  -
Профиль   Отправить e-mail  

rsa - проблемы с декодированием

Проблема проявляется при маленьких значениях n. n должно быть больше 54 иначе вылезут ошибки.

P.S. Вместо int(i)**self.e%self.n лучше использовать pow(int(i), self.e, self.n), для небольших чисел это некритично, а вот в реальных RSA вычислениях намного быстрее.

P.P.S. ИМХО код переписать, он просто ужасен.



Офлайн

#6 Апрель 21, 2010 20:17:04

akolesnikov
От:
Зарегистрирован: 2009-10-26
Сообщения: 36
Репутация: +  0  -
Профиль   Отправить e-mail  

rsa - проблемы с декодированием

спасибо, я уже нашел косяки, теперь все работает.
а что ужасного в коде?



Офлайн

#7 Апрель 21, 2010 20:19:17

akolesnikov
От:
Зарегистрирован: 2009-10-26
Сообщения: 36
Репутация: +  0  -
Профиль   Отправить e-mail  

rsa - проблемы с декодированием

и еще, почему n должно быть меньше 54? это относится конкретно к моему коду или вообще к алгоритму? во многих примерах алгоритма юзают маленький n, 33 например



Офлайн

#8 Апрель 21, 2010 20:52:24

Zubchick
От:
Зарегистрирован: 2009-07-08
Сообщения: 613
Репутация: +  0  -
Профиль   Отправить e-mail  

rsa - проблемы с декодированием

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



Офлайн

#9 Апрель 21, 2010 20:53:20

akolesnikov
От:
Зарегистрирован: 2009-10-26
Сообщения: 36
Репутация: +  0  -
Профиль   Отправить e-mail  

rsa - проблемы с декодированием

это я частично реализовал.



Офлайн

#10 Апрель 21, 2010 22:21:49

Ed
От:
Зарегистрирован: 2008-12-13
Сообщения: 1032
Репутация: +  13  -
Профиль   Отправить e-mail  

rsa - проблемы с декодированием

akolesnikov
а что ужасного в коде?
Там по идее достаточно нескольких функций - gen_keys(), encrypt(text, key), decrypt(text, key), а вы наворотили там этот класс, свалили все туда, а потом еще снаружи в нем атрибуты устанавливаете.
Не обижайтесь, но код выглядит просто как издевательство над языком.
Могу помочь подправить, если хотите.



Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version