in name of zero

                       INOZ, issue #1, 20 nov. 2001


                           Некоторые идеи о 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, к разрядам меньшим занимающего
          ;не прибавляется ничего.
  Таким  образом для проведения нам потребуется минимальное кол-во памяти
 и ресурсов компьютера.