/*-----------------------------------------------------------------------*/
/* R I N G 0, I S S U E # 1 */
/*-----------------------------------------------------------------------*/
Некоторые идеи о RSA
by Dr. Hanibal Lector (Hanibal) // SBVC
Для тех кто не знает алгоритма RSA:
1.Выбираются два больших простых числа P и Q.
2.Определяется первая часть открытого ключа N=P*Q.
3.Определяется вторая часть открытого ключа - выбирается четное
(меньшее P,Q) число E, взаимно простое с числом (P-1)*(Q-1),
заметим, что (P-1)*(Q-1)=P*Q*(1-1/P)(1-1/Q).
4.Определяется закрытый ключ D=1/E MOD ((P-1)*(Q-1))
Шифровка:
C[i]=(S[i])^E MOD N
Расшифровка:
P[i]=(C[i])^D MOD N
Подумал я вот тут и захотелось мне написать собственную реализацию RSA,
да чтоб ключик по больше был :)),но тут возникло несколько проблем:
1.Генерация больших простых чисел.
2.Собственно генерация ключей.
3.Оперирование с такими большими числами.
Генерация больших чисел:
Думал, думал и....(не передумал Ж:), а просто решил что ведь можно
число представлять себе на уровне битов->байтов->слов и т.д. по этому и
генерировать можно какую нибудь переменную на этом же уровне.Я как
отступник от всего традиционного взял десятичную систему счисления и
сразу стало видно что любое число (!) представляется из комбинации чифр
0-9 таким образом самым большим числом в двочном представлении будет
1001(9) ,таким образом можно генерировать числа 1xxx,1xx,1x,x, вот и вся
математика , получается что генерация допустим числа Q и числа P это
всего лишь цикл до Counter ,где коунтер это число цифр в числе.
Проверка на "простоту" и вычисление остатка от деления:
Как же происходит проверка на простоту,я например не испоьзую никакие
алгоритмы а просто раскладываю на множители, то бишь делаю как бы цикл в
котором избольшого числа вычитаю меньшее числа, я все думал как же можно
уменьшить или оптимизировать этот процесс и пришел к следующему:Допустим
большое число у нас X, а Y множество натуральных чисел меньших данного
числа, тогда как уменьшить кол-во эл-ов в данном множестве? Проверка же
будет следующая:
если X MOD Y[i] = 0, то число не простое .
Теперь стало видно что наименьшим эл-ом в Y{..} будет 3, так как 2
четное а при генерации мы делаем проверку полседне цифры и генереруем её
до тех пор пока она не станет нечетной. Следовательно счетчик цикла
обработки множествава Y{..} можно приравнять к (X-1)/2. Это в двое
увеличит скорость обработки.Поехали дальше, как же нам работать с
громадными числами в обыкновенной школьной математике объясняется что
существует всего две арифметических операции плюс и обратная ему минус,
а остальные можно выразить через них:
5*4=5+5+5+5(4раза)=4+4+4+4+4(5раз)
12/6=12-6-6(2раза)
12/3=12-3-3-3-3(4раза)
Таким образом мы легко можем оперировать этими пояниями,а вот как же
использовать сложение и вычитание в больших числах?Да,просто все
наверное помнять операции в столбик вот это и есть самая гениальнейшая
мысль:
Умножение:
123456789 ;
x ;
000000005 ;
_________ ;
123456789 ;
x ; 9*5=45
000000005 ; ^^
_________ ; ||
123456785 ; | берем цифру из единичного разряда
x ; |
000000005 ; дополнительно осталось 4 во второй разряд, заносим в регистр OST
_________ ;
123456785 ; 8*5=40
x ; ^^
000000005 ; ||
; |берем цифру из единичного разряда и складываем
; | с регистром OST
; |
; дополнительно осталось 4 в третий разряд,
; заносим в регистр OST
Деление представляет из себя вычитание в цикле WHILE NOT BELOW (Пока
делимое не станет меньше делителя).
Вычитание:
987654321 ;
- ;
123456789 ;
_________ ;
98765432x ; x=1-9
- ; ^ ^
123456789 ; | |
_________ ; | -----------------------------
9876543x2 ; | если |
- ;число из первого разряда меньше числа из
123456789 ;первого разряда вычиаемго то
_________ ;занимаем один десяток у чила на разряд больше
и т.д. ;если нельзя занять(ноль),то берем у числа на ещё один
;разряд больше и так дотех пор пока нельзя будет занять.
;Но ко всем последующим разрядам до занимающего прибавляется
;не 10 единиц разряда а 9, к разрядам меньшим занимающего
;не прибавляется ничего.
Таким образом для проведения нам потребуется минимальное кол-во памяти
и ресурсов компьютера.