В. Семенов Снова о шифровании: быстрый алгоритм вычисления модульной экспоненты Листинг name MOD_DLN ; *********************************************************** ; * Вычисление модульной экспоненты. Версия для IBM XT/AT * ; * (С) Семенов В.Л. 1993г. * ; *********************************************************** ; трансляция программы : tasm MOD_DLN ; создание сом файла : tlink /t MOD_DLN Dlina equ BYTE PTR ds:[bx] kon_pr equ offset prom ; seg_a segment byte public assume cs:seg_a, ds:seg_a org 100h ; COM file ; MOD_DLN proc far ; ------------------------------------ ; Ввод модуля,степени и числа ; ------------------------------------ START: mov ax,cs mov es,ax mov ds,ax mov dx,offset zap_mod ;Ввод значения mov bx,offset rez ;модуля CALL CIFR mov dx,offset zap_step ;Ввод значения mov bx,offset chis ;степени CALL CIFR mov bx,offset rez ;Преобразование введённых значений mov si,offset chis ;для ускорения последующих CALL DmultIni ;вычислений mov dx,offset zap_chis ;Ввод значения mov bx,offset chis ;числа CALL CIFR mov word ptr rez,101h ;Установка начального значения = 1 mov word ptr rez+2,0 ;************************************** ; Блок вычисления модульной экспоненты ;************************************** mov si,offset M_ST mov adr_t_st,si cmp byte ptr [si],0 jz C_rez_N cld mov si,offset chis ; Пересылка первой степени mov di,offset rez ; при необходимости mov cx,48 rep movsw C_rez_N: mov cx,kol_ch_raz mov t_st,cx C_REZ: dec t_st jz ZAV_PR mov bx,offset chis mov bp,offset chis ; Умножением числа самого на себя CALL Dmult ; получаем квадрат числа inc adr_t_st mov si,adr_t_st cmp byte ptr [si],0 jz C_REZ mov bx,offset rez ; Умножаем результат на число mov bp,offset chis ; степени разложения CALL Dmult jmp short C_REZ ;************************************** ; ------------------------------------ ; Завершение работы программы ; ------------------------------------ ZAV_PR: mov di,offset zap_mod ; Вывод полученного mov bx,offset rez ; результата в символьном xor cx,cx ; виде SL_CIF: push cx xor ch,ch xor ah,ah mov cl,dlina mov si,cx ; ! add si,bx ;--- Определение старшего разряда числа mov dl,10 mov al,[si] div dl mov [si],al cmp al,0 jne SL_met dec dlina SL_met: dec cx jz kon_dlc dec si mov al,[si] div dl mov [si],al jmp SL_met kon_dlc: pop cx inc di mov [di],ah ; Остаток от деления длинного inc cx ; целого на 10 cmp dlina,1 jne SL_CIF pov_cif: xor ah,ah ; Обработка последнего байта, div dl ; оставшегося от последовательных inc di ; делений длинного числа mov [di],ah inc cx cmp al,0 jne pov_cif ; mov dx,offset zap_rez mov ah,9 ; DS:DX - указатель на строку сообщения int 21h ; Вывод сообщения на экран дисплея std mov si,di BYB_CIF: lodsb xor al,30h mov ah,14 int 10h ; Вывод цифры на дисплей loop BYB_CIF mov al,10 int 10h ; mov ah,4Ch ; Вернуться в DOS int 21h ;--------------------------------- ; Область данных ;--------------------------------- zap_mod db 'Все введённые числа не должны содержать более 225 цифр' db 10,13,'Введите модуль : $' zap_step db 10,13,'Введите степень : $' zap_chis db 10,13,'Введите число : $' chis db 96 dup (0) rez db 96 dup (0) zap_rez db 10,13,'Результат : $' MOD_DLN endp ; ------------------------------------ ; Подпрограмма ввода десятичного числа с клавиатуры ; Результат ввода возвращается по смещению, заданному регистром BX ; Признак конца числа - любой символ, отличный от цифры ; Формат вводимого числа: ; 1-й байт - реальное количество байтов, занимаемых числом ; Первый байт не учитывается в длине поля числа ; Для размещения 225 цифр необходимо поле длиной 96 байтов ; ------------------------------------ CIFR proc near mov ah,9 ; DS:DX - указатель на строку сообщения int 21h ; Вывод сообщения на экран дисплея ; xor ax,ax ; Обнуляем регистр накопления результата inc ax mov [bx],ax mov dl,10 CIKL: mov ah,1 ; Считываем символ с клавиатуры и отображаем int 21h ; на экране дисплея cmp al,30h jb end_cifr ; Введённый символ не цифра cmp al,39h ja end_cifr ; Введённый символ не цифра and ax,000Fh ; Преобразуем символ в десятичную цифру xor ch,ch ; Добавим введённую цифру mov si,bx ; к содержимому регистра inc si ; накопления, умноженному на 10 mov cl,dlina push bx mov bx,ax mov al,[si] mul dl add ax,bx xor bh,bh jmp met_k met_n: mov bl,ah mov al,[si] mul dl add ax,bx met_k: mov [si],al inc si loop met_n pop bx cmp ah,0 je CIKL inc Dlina mov [si],ah jmp CIKL ; Переходим к вводу следующего символа ; end_cifr: xor ax,ax ; Создание защитного mov [si+1],ax ; интервала ret CIFR endp ; M_ST db 96*8-92h dup(0) ; Будем использовать часть кода ; подпрограммы DmultIni ; для буфера распакованной степени ; ; Подпрограмма подготовки постоянных данных о модуле и степени ; выполняется один раз за время работы программы ; Обеспечивает ускорение операций возведения в степень по модулю ; BX - адрес строки со значением модуля ; SI - адрес строки со значением степени DmultIni proc near push si ; Вычисление длины модуля в битах mov si,bx xor ax,ax mov al,dlina add si,ax ; Начало значащей части модуля mov kol_bait_mod,ax cld mov cx,8 ; Выравнивание числа модуля по mov al,[si] ; правой границе NACH_b: rol al,1 jc kon_b loop nach_b KON_b: mov al,8 sub al,cl mov kol_sdv,al ;Определение количества сдвигов mov dx,cx shl cl,1 shl cl,1 mov kol_cx,cl ; mov ax,Kol_bait_mod inc ax mov di,offset Mind+2 mov cx,9 ; Заполнение массива длины z_zn: stosw dec dx jnz sl_zn dec ax sl_zn: inc di inc di loop z_zn ; mov di,mind_kz ; Адрес выровненного массива add di,kol_bait_mod dec di mov bp,di mov cl,kol_sdv mov dx,kol_bait_mod c_baz: dec si ; Получение числа, выровненного mov ax,[si] ; на левую границу байта в dec dx ; старшем разряде jz k_baz rol ax,cl mov [di],ah dec di jmp short c_baz k_baz: xor al,al rol ax,cl mov [di],ah ; Заполнение массива возможных фаз сложения mov dx,7 mov bx,offset mind_kz std Z_mas_n: mov si,bp sub bp,96 mov di,bp dec bx dec bx mov cx,[bx] ; Длина получаемого числа dec bx ; Установка адреса в массиве dec bx ; управления для записи ; адреса начала числа z_mas_sd: lodsb rcr al,1 stosb loop z_mas_sd inc di mov [bx],di ; Адрес начала младшего разряда числа dec dx jnz z_mas_n ; pop bx ; Обработка степени mov Kol_ch_raz,dx ; Получение распакованного mov si,bx ; массива для организации cld ; бинарного метода возведения mov dl,dlina ; в степень mov di,offset M_ST N_cik_st: inc si mov ah,[si] mov cx,8 Cik_st: shr ah,1 rcl al,1 and al,1 stosb inc Kol_ch_raz loop Cik_st dec dx jnz N_cik_st ; C_kon: dec di cmp byte ptr [di],cl jnz kon_ini dec Kol_ch_raz jmp short C_kon kon_ini: ret DmultIni endp ; kol_ch_raz dw 0 adr_t_st dw 0 tek_cx dw 0 t_st dw 0,0 Mfaz db 96*8 dup(0) Mind dw offset Mfaz+96*7 dw 15 dup (0) Mind_kz dw offset Mfaz+96*7 dw 0,0 prom db 192 dup (0) adn_um dw 0 tdlmn dw 0 ind_zav db 0 kol_bait_mod dw 0 kol_sdv db 0 kol_cx db 0 MPR db 0,4,8,8,12,12,12,12 ; Формируя данный массив db 8 dup (16) ; с учётом значения модуля db 16 dup (20) ; деления, можно добиться db 32 dup (24) ; некоторого ускорения db 64 dup (28) ; работы программы db 128 dup (32) ; ; Подпрограмма длинного умножения двух чисел по модулю ; Модуль задаётся подпрограммой DmultIni один раз в ; начале работы программы ; BX - смещение множимого (результата) ; BP - смещение множителя Dmult proc near xor cx,cx ; Вычисление размерностей xor dx,dx ; чисел множимого и xor ax,ax ; множителя mov ind_zav,ch mov dl,dlina mov al,dl inc dl shr dl,1 mov tek_cx,dx push bx inc bx mov adn_um,bx mov cl,[bp] add ax,cx mov di,kon_pr mov tdlmn,ax inc cx shr cx,1 push cx add cx,dx cld ; Обнуление промежуточного xor ax,ax ; числа с результатом умножения rep stosw pop cx mov bx,offset prom - 2 sub bx,adn_um jmp short cik_tdl ; ; Обработка знака вынесена за границу цикла, так как встречается редко obr_per: add word ptr [bx+si+2],1 jnc kon_ck push si ; Вероятность выполнения PR_per: add si,2 ; этого участка программы add word ptr [bx+si+2],1 ; практически равна 0, jc PR_per ; однако на всякий случай pop si ; учтём эту возможность jmp kon_ck ; cik_tdl: inc bp push cx mov di,[bp] inc bp mov si,adn_um mov cx,tek_cx lodsw cikl_umn: mul di ; Цикл перемножения по байтам множителя add [bx+si],ax ; lodsw ; adc [bx+si],dx jc obr_per ; Обработка знака переноса при сложении kon_ck: loop cikl_umn inc bx inc bx pop cx loop cik_tdl ; mov cx,tdlmn ; Максимально возможная длина результата mov di,kon_pr add di,cx ; Вычисление остатка от dec di ; деления результата умножения xor bh,bh ; на модуль sub cx,kol_bait_mod ja cokr_dl je b_bitz add cx,kol_bait_mod jmp short kon_umn Cokr_dl: mov dx,cx ; Вычисление модульного сравнения B_bit: mov bl,[di] cmp bl,bh je kon_bit mov cl,[bx+offset MPR] mov ax,offset b_bit JMP short Ud_bit ; Вызов подпрограммы удаления ; старшего бита KON_bit: dec di dec dx jnz b_bit ; B_bitz: mov bl,[di] ; Сокращение битового mov cl,[bx+offset MPR] ; остатка в байте cmp cl,kol_cx jb kon_dop je pr_ca mov ax,offset b_bitz JMP short Ud_bit pr_ca: inc ind_zav mov ax,offset kon_dop JMP short Ud_bit ; Остаток больше модуля ; kon_dop: mov cx,kol_bait_mod kon_umn: mov di,adn_um ; Пересылка результата умножения cld ; в поле множителя pop bx mov dlina,cl mov si,kon_pr rep movsb mov [di],cx ; Очистка поля за концом числа dec di ; Удаление незначащего 0 cmp [di],ch ; из старших разрядов jnz nud_razr ; числа dec dlina nud_razr: ret ; ; Подпрограмма вычитания модуля из промежуточного числа ; CX - текущее место значащего бита промежуточного числа ; DI - адрес начала значащей части промежуточного числа Ud_bit: push ax push di add cx,offset mind mov bp,cx mov si,[bp] ; Адрес строки mov cx,[bp+2] ; Длина строки add si,cx dec si std ; Определение c_srav: lodsb ; сдвига, с которого cmp al,[di] ; начинать вычитание ja sl_sdvig ; строки модуля jb rab dec di loop c_srav jmp short rab sl_sdvig: sub bp,4 ; Необходимо взять cmp ind_zav,0 ; для вычитания jz rab ; число вдвое меньше pop di ret rab: mov si,[bp] mov cx,[bp+2] pop di mov bp,di inc cx sub bp,cx shr cx,1 ;Длина в байтах sub bp,si cld c_bych: lodsw sbb [bp+si],ax loop c_bych ret Dmult endp seg_a ends end start