home *** CD-ROM | disk | FTP | other *** search
/ Shareware Supreme Volume 6 #1 / swsii.zip / swsii / 215 / DDJ9301.ZIP / LUC.ASC < prev    next >
Text File  |  1992-12-08  |  15KB  |  474 lines
  1. _LUC PUBLIC-KEY ENCRYPTION_
  2. by Peter Smith
  3.  
  4.  
  5. [LISTING ONE]
  6.  
  7. { To calculate Ve(P,1) modulo N }
  8.  Procedure LUCcalc;
  9.  {Initialise}
  10.  BEGIN
  11.  D := P*P - 4; ut := 1; vt := P; u := ut; v := vt;
  12.  If not odd(e) then BEGIN u := 0; v := 2; END;
  13.  e := e div 2;
  14.  {Start main}
  15.  While e > 0 do
  16.    BEGIN
  17.    ut := ut*vt mod N; vt := vt*vt mod N;
  18.    If vt < 3 then vt := vt + N;
  19.    vt := vt - 2;
  20.    If odd(e) then
  21.      BEGIN
  22.      c := (ut*v + u*vt) mod N;
  23.      v := (vt*v + D*u*ut) mod N;
  24.      If odd(v) then v := v + N; v := v/2;
  25.      If odd(c) then c := c + N; u := c/2;
  26.      END;
  27.    e := e div 2;
  28.    END;
  29.  END;    {LUCcalc}
  30.  
  31. { The required result is the value of v.}
  32.  
  33.  
  34. [LISTING TWO] 
  35.  
  36.  
  37. Procedure wiluc  {   V = V(M) Mod N, the Mth Lucas number(P,1) }
  38. Var
  39.                     V,Vb,P,Vf,N,M,NP, Vd, Vf : LargeInteger ;
  40.                     carry, high_bit_set      : boolean ;
  41.                     bz                        : word ;
  42.   BEGIN
  43.   Va := 2 ;   { V[0] }  Vb = P ;   { V[1] }
  44.   NP := N - P; bz := bits(M) -1 ; { test bits from high bit downwards }
  45.   For j := 1 to bz do
  46.       BEGIN
  47.       Vc := Vb * Vb; Vf = Vc ; If Vf < 2 then Vf := Vf + N
  48.       Vf := Vf - 2; Vd := Va * Vb
  49.       {  Vc := V, Vd := V*Vb, Vf := V-2}
  50.      If high_bit_set Then
  51.           BEGIN
  52.           Vb := P * Vc; If Vb < Vd then Vb := Vb + N; Vb := Vb - Vd;
  53.           If Vb < P then Vb := Vb + N; Vb := Vb - P; Va := Vf
  54.           END ;
  55.      Else BEGIN { "even" ie high bit not set }
  56.           Va := Vd; If Va < P then Va := Va + N; Va := Va - P;
  57.           Vb := Vf;
  58.           END ;
  59.      High_bit_set := next_bit_down(M);
  60.      {This boolean function determines the setting of the next bit down}
  61.      Va := Va Mod N; Vb := Vb Mod N
  62.      END ; { for j to bz }
  63. END ; {wiluc}
  64.  
  65.  
  66. [LISTING THREE]
  67.  
  68. { Pseudocode for splitting decryption/signing over p and q 
  69.   (N = p*q) }
  70. Procedure hafluc ( var s,p,q,m,e : LargeInteger ; qix : word ) ;
  71. var                            ep,emq,
  72.                                temp,pi,qi,
  73.                                b,n,pa,qa : LargeInteger ;
  74.  
  75. { This procedure applies only to decipherment and signing, where the primes
  76.   making up the modulus N ( = p * q) are known (or can be easily deduced, 
  77.   since both keys are known). Applying it allows us to halve the amount of 
  78.   work. Encipherment is usually done with a small key - standard is 65537. }
  79.   Begin
  80.   Qpr (pa,qa,p,q,m,qix ) ; {} {assumes qix already calculated }
  81.   ep  = e ;              ep  = ep  Mod pa
  82.   emq = e ;   emq  = emq Mod qa
  83.   mp  = m ;    mp  = mp Mod p
  84.   mq  = m ;    mq  = mq Mod q
  85.   wiluc(q2,mq,emq,q) ;        wiluc(p2,mp,ep,p) ;
  86.   if p2 < q2 then
  87.       Begin
  88.       temp = q         q  = p    p  = temp
  89.       temp = q2        q2 = p2   p2 = temp
  90.       End ;
  91.   temp = p2   temp = temp - q2
  92.   n = p * q
  93. { Solve with Extended Euclidean algorithm qi = 1/q Mod p. The algorithm 
  94. for the Extended Euclidean calculation can be found in Knuth. }
  95.   r = temp * p
  96.   r = r mod N
  97.   s = r * qi
  98.   s = s Mod n
  99.   s = s + p2
  100. End ; { hafluc }
  101. Procedure SignVerify ;
  102.   Begin
  103.   h4 = 4
  104.   p = large prime...
  105.   q = large prime...
  106.   n = p * q
  107.   bz := bits(n) ;
  108.     {write(cf,'  generate 4 keysets (d,e)  for p1,q1') ;}
  109. {
  110.       qix table for T[qix]
  111.      Convention for qix
  112.  This calculation is explained below.
  113.    Lehmer totient      qix   Legendre values for p  and   q
  114.    i.e. T[qix] = LCM
  115.    (p - 1),(q - 1)     1                         1        1
  116.    (p - 1),(q + 1)     2                         1       -1
  117.    (p + 1),(q - 1)     3                        -1        1
  118.    (p + 1),(q + 1)     4                        -1       -1              
  119.     e = encryption key,  small prime eg 65537
  120.     mu = message as large integer less than n
  121.     Solve e * d[qix] = 1 Mod T[qix] using Extended Euclidean Algorithm
  122.     where T[qix] is lcm(p1,q1), the Lehmer totient function of N
  123.     with repect to mu, according to the above table.
  124.     This gives 4 possible values of d, the decryption/signing key.
  125.     The particular value used depends on the message mu, as follows:
  126.     Let D = mu2 - 4. Calculate the Legendre values of D with respect to
  127.     both p and q. This value is -1 if D is a quadratic non-residue of
  128.     p (or q), and equal to 1 if D is a quadratic residue of p (or q).
  129.     N.B. This part is the most difficult part of LUC! Take care.
  130.  
  131.     Signing (Deciphering):
  132.     hafluc (a,pu,qu,mu,d,qix) 
  133.  
  134.     Verifying (Enciphering):
  135.     Use Wiluc.
  136. End.
  137.  
  138.  
  139. [LISTING FOUR]
  140.  
  141. Algorithm D in 32-bit Intel assmbler
  142. Author: Christopher T. Skinner
  143. Short version of Mod32.Txt with scalings just as comments
  144.                Modulus routine for Large Integers
  145.                         u = u Mod v
  146. Based on:
  147. D.E.Knuth  The Art of Computer Programming
  148.            Vol 2 Semi-Numerical Algorithms 2ed 1981
  149.            Algorithm D page 257
  150. We use a Pascal Type called "har" ( for "hexadecimal array")
  151. Type
  152.             har = Array[0..255] of byte ;
  153. Var         u,v : har ;
  154. Note that u[0] is the length of u and that the
  155. integer begins in u[1]
  156. It is desirable that u[1] is on a double word boundary.
  157.  
  158. ; Turbo Pascal Usage:      ( Turbo Pascal v6.0)
  159. ; {$L Mod32a}   { contains mod32 far }
  160. ; {$F+}   { far pointers }
  161. ; procedure Mod32 ( var u,v : har ) ;
  162. ; Turbo Assembler code: (TASM v2.01)--requires 32-bit chip ie 386 or 486
  163. ; nb FS and GS can be used as temporary storage. Don't try to use them as 
  164. ; segment registers because Windows 3.0 restricts their allowed range, even
  165. ; after you have finished out of Windows. You will hang for sure, unless you
  166. ; have used a well-behaved protected-mode program to reset them, or cold boot.
  167.  
  168. Data    Segment Word Public Use16
  169.     vdz     dw ?        ; size  v    words
  170.     va  dd ?            ;     hi dword v
  171.     vb  dd ?            ; 2nd     "    v
  172.     vi  dw ?        ; ^v[1]
  173.         savdi   dw ?            ; used in addback
  174. Data    EndS
  175.  
  176. Code    Segment Word Public  Use16
  177.     Assume  cs:Code, ds:Data ,es:Nothing
  178.         Public  mod32
  179. ; Pascal Parameters:
  180. u   Equ DWord Ptr ss:[bp+10]      ; Parameter 1 of 2   (far)
  181. v       Equ DWord Ptr ss:[bp+ 6]      ; parameter 2 of 2
  182. uof     equ word ptr  ss:[bp+10]
  183. vinof   equ word ptr  ss:[bp+ 6]
  184.  
  185. mod32   Proc    far
  186.     push bp
  187.     mov  bp,sp
  188.         push di
  189.         push si
  190.         push ds          ; save the DS
  191.  
  192.         ; Before using Mod32 check that:
  193.         ;     v > 0
  194.         ;     v < u         u <= 125 words
  195.         ;     v[0] is a multiple of 4   and at least 8
  196.         ;     v[top] >= 80h           (may need to scale u & v)
  197.         ;     make u[0] = 0 Mod 4     (add 1..3 if required)
  198. domod:
  199.         ; now point to our v
  200.         mov ax,seg v
  201.         mov ds,ax
  202.         assume ds:Data   
  203.         mov si, offset v
  204.         cld
  205.         assume es:Nothing
  206.     xor ah,ah
  207.     mov al,es:[di]   ; ax = size of u in bytes    "uz"
  208.     mov cx,ax        ; cx = uz
  209.     mov bx,ax        ; bx = uz
  210.     mov al,[si]
  211.     mov dx,ax    ; dx  = size v bytes
  212.     shr ax,2
  213.     mov vdz,ax   ; vdz    "     dwords   vz = 0 mod 4
  214.     sub bx,dx        ; bx = uz - vz  difference in bytes
  215.     mov ax,bx        ; ax = uz - vz
  216.     sub ax,3     ; ax = uz - vz - 3     ->  gs
  217.     sub cx,3     ; cx =  uz - 3
  218.     add cx,di        ; cx = ^top dword u
  219.     add ax,di
  220.     mov gs,ax    ; gs = ^(uz-vz-3)  u start   (by -4  down to 1)
  221.         inc di
  222.         mov fs,di    ; fs = uf = ^u[1] , end point
  223.     inc si
  224.     mov vi,si    ; vi = ^v[1]
  225.     add si,dx
  226.     mov eax,[si-4]
  227.     mov va,eax   ;  va = high word of v
  228.     mov eax,[si-8]
  229.     mov vb,eax       ;  vb = 2nd highest word v
  230.     mov di,cx    ; set di to ut , as at bottom of loop
  231. d3:
  232.     mov edx,es:[di]  ; dx is current high dword of u
  233.     sub di,4
  234.         mov eax,es:[di]  ; ax is current 2nd highest dword of u
  235.     mov ecx,va
  236.     cmp edx,ecx
  237.     jae  aa          ; if high word u is 0 , never greater than
  238.     div ecx      ;          mov ebx,eax
  239.         mov esi,edx  ; si = rh
  240.     jmp short ad     ; Normal route -- -- -- -- -->
  241. aa:     mov eax,0FFFFFFFFh
  242.     mov edx,es:[di]  ; 2nd highest wrd u
  243.     jmp short ac
  244. ab: mov eax,ebx      ; q2
  245.     dec eax
  246.     mov edx,esi      ;  rh
  247. ac: mov ebx,eax      ; q3
  248.     add edx,ecx
  249.     jc d4        ; Knuth tests overflow,
  250.     mov esi,edx
  251. ; normal route:
  252.  ad:
  253.         mul vb       ; Quotient by 2nd digit of divisor
  254.     cmp edx,esi  ; high word of product : remainder
  255.     jb  d4           ; no correction to quot, drop thru to mulsub
  256.         ja  ab           ; nb unsigned use ja/b not jg/l
  257.     cmp eax,es:[di-4] ; low word of product : 3rd high of u
  258.     ja  ab
  259. d4:          ; Multiply & subtract * * * * * * *
  260.     mov cx,gs
  261.     mov di,cx    ; low start pos in u for subtraction of q * v
  262.         sub cx,4
  263.         mov gs,cx
  264.         xor ecx,ecx
  265.     Mov  cx,vdz  ; word count for q * v
  266.         mov  si,vi   ; si points to v[1]
  267.         xor ebp,ebp      ; carry 14Oct90 bp had problems in mu-lp
  268.         even
  269. ;    ** ** ** ** **  **  **  **
  270. ba:     lodsd        ; eax <- ds[si]
  271.     mul ebx      ; dx:ax contains product   carry set if dx > 0
  272.         add eax,ebp
  273.         adc edx,0
  274.     sub es:[di],eax
  275.         adc edx,0
  276.         mov ebp,edx
  277.         add di,4
  278.     loop ba      ; dec cx , jmp if not 0
  279. ; .. .. .. . .. .. . .. .. . .. . . ..
  280.         sub es:[di],edx
  281.         jnc d7
  282.  
  283.     mov si,vi    ;  add back (rare)
  284.         mov savdi,di
  285.     mov di,gs
  286.         add di,4
  287.     clc
  288.     mov cx,vdz
  289. bb:     lodsd        ; eax = ds[si]   si + 2
  290.     adc es:[di],eax
  291.         inc di
  292.         inc di
  293.         inc di
  294.         inc di
  295.         loop bb
  296.         xor eax,eax
  297.         mov es:[di],eax
  298.         mov di,savdi
  299.         ; test with:
  300.         ; 1,00000000,00000000,00000001/ 80000000,00000000,00000001
  301. d7:
  302.     mov bx,fs     ; fs ^u[1]
  303.         mov ax,gs     ; gs = current u start position
  304.     cmp ax,bx     ; current - bottom
  305.     jb d8
  306.         sub di,4
  307.     jmp d3
  308. d8:
  309. ; here we would scale u down if it had been scaled up
  310. quex:                 ; quick exit if v < u
  311.         cld              ; just in case
  312.         pop ds
  313.         pop si
  314.         pop di
  315.         pop bp
  316.     ret 8       ; 2 pointers = 4 words = 8 bytes
  317. mod32   EndP        ; 
  318. Code    Ends
  319.     End
  320.  
  321.  
  322. [LISTING FIVE]
  323.  
  324. Algorithm D in 16-bit Intel assembler
  325. Author: Christopher T. Skinner
  326.    mod16.txt 21 Au8 92     16 bit modulus
  327. ; divm  Modulus                                           
  328. Data    Segment Word Public
  329.     vwz     dw ?        ; size  v    words
  330.     va  dw ?            ;     hi word v
  331.     vb  dw ?            ; 2nd    "    v
  332.     vi  dw ?        ; ^v[1]
  333.     uf  dw ?        ; ^u[3]
  334.     uz  dw ?            ; size u byte
  335.     vz  dw ?             ;   "   v  "
  336.     ua      dw ?        ; ^( u[0] + uz - vz -1 ) , mul sub start
  337.     ut  dw ?            ; ^ u[topword]
  338.     qh      dw ?
  339.     uzofs   dw ?        ; ttt
  340.     vzofs   dw ?        ; ttt
  341. Data    EndS
  342. Code    Segment Word Public
  343.     Assume  cs:Code, ds:Data
  344.         Public  diva
  345.  
  346. u   Equ DWord Ptr [bp+10]       ; ES:DI
  347. v       Equ DWord Ptr [bp+6]        ; DS:SI
  348.     ; NB v Must be Global, DS based...
  349. diva    Proc    far
  350.     push bp
  351.     mov  bp,sp
  352.         push ds
  353.     cld     ; increment lodsw in mulsub
  354.     lds si,v
  355.         les di,u
  356.     xor ah,ah
  357.     mov al,es:[di]  ; ax = uz size of u in bytes N.B. uz is not actually used
  358.     mov cx,ax       ; cx = uz
  359.     mov bx,ax       ; bx = uz
  360.     mov al,ds:[si]
  361.     mov dx,ax   ; dx  = size v bytes
  362.     shr ax,1
  363.     mov vwz,ax  ; vwz    "     words
  364.     sub bx,dx       ; bx = uz - vz  difference in bytes
  365.     mov ax,bx       ; ax = uz - vz
  366.     dec ax      ; ax = uz - vz - 1     ->  ua
  367.     dec cx      ; cx =  uz - 1
  368.     add cx,di       ; cx = ^top word u
  369.     mov ut,cx   ; ut = ^top word u
  370.     add ax,di
  371.     mov ua,ax   ; ua = ^(uz-vz-1)  u start   (by -2  down to 1)
  372.         inc di
  373.     mov uf,di   ; uf = ^u[1] , end point
  374.     inc si
  375.     mov vi,si   ; vi = ^v[1]
  376.     add si,dx
  377.     mov ax,ds:[si-2]
  378.     mov va,ax   ;  va = high word of v
  379.     mov ax,ds:[si-4]
  380.     mov vb,ax       ;  vb = 2nd highest word v
  381.     mov di,cx   ; set di to ut , as at bottom of loop
  382. d3:
  383.     mov dx,es:[di]          ; dx is current high word of u
  384.     dec di
  385.     dec di
  386.     mov ut,di
  387.         mov ax,es:[di]        ; ax is current 2nd highest word of u
  388.     mov cx,va
  389.     cmp dx,cx
  390.     jae  aa   ;if high word u is 0 , never greater than
  391.     div cx          ;  
  392.         mov qh,ax
  393.         mov si,dx       ; si = rh
  394.     jmp ad          ; Normal route -- -- -- -- -->
  395. aa:     mov ax,0FFFFh
  396.     mov dx,es:[di]      ; 2nd highest wrd u
  397.     jmp ac
  398. ab: mov ax,qh
  399.     dec ax
  400.     mov dx,si       ;  rh
  401. ac: mov qh,ax
  402.     add dx,cx
  403.     jc d4           ; Knuth tests overflow,
  404.     mov si,dx
  405. ad:     mul vb          ; Quotient by 2nd digit of divisor
  406.     cmp dx,si       ; high word of product : remainder
  407.     jb  d4          ; no correction to quot, drop thru to mulsub
  408.         ja  ab          ; nb unsigned use ja/b not jg/l
  409.     cmp ax,es:[di-2]    ; low word of product : 3rd high of u
  410.     ja  ab
  411. d4:         ; Multiply & subtract * * * * * * *
  412.     mov bx,ua
  413.     mov di,bx   ; low start pos in u for subtraction of q * v
  414.     dec bx
  415.     dec bx      ;
  416.     mov ua,bx
  417.     Mov  cx,vwz ; word count for q * v
  418.         mov  si,vi  ; si points to v[1]
  419.     mov bx,qh
  420.         xor bp,bp
  421. ;    ** ** ** ** **  **  **  **
  422. ba:     lodsw       ; ax <- ds[si]   si + 2  preserve carry over mul ?
  423.     mul bx      ; dx:ax contains product   carry set if dx > 0
  424.     add dx,bp
  425.         xor bp,bp
  426.     sub es:[di],ax
  427.     inc di
  428.     inc di
  429.     sbb es:[di],dx
  430.     rcl bp,1
  431.     loop ba     ; dec cx , jmp if not 0
  432. ; .. .. .. . .. .. . .. .. . .. . . ..
  433.         rcr bp,1
  434.         jnc d7
  435.  
  436.     mov si,vi   ;  add back (rare)
  437.     mov di,ua
  438.        inc di
  439.     inc di
  440.     clc
  441.     mov cx,vwz
  442. bb:    lodsw        ; ax = ds[si]   si + 2
  443.     adc es:[di],ax
  444.     inc di
  445.     inc di
  446.     loop bb
  447.     mov cx,ut
  448.     add cx,4
  449.     sub cx,di
  450.     shr cx,1        ; word length of u
  451. bc:    mov Word Ptr es:[di],0
  452.        inc di
  453.     inc di
  454.        loop bc  ;
  455.     dec di      ;
  456.     dec di      ;
  457.     clc
  458. d7:
  459.     mov ax,uf
  460.     cmp ua,ax
  461.     jb d8
  462.     dec di      ; New these are suspicious, with an add back and a
  463.     dec di      ; New
  464.     jmp d3
  465. d8:
  466.              cld   ; just in case
  467.        pop ds
  468.     pop bp
  469.     ret 8       ; 2 pointers = 4 words = 8 bytes ???
  470. diva    EndP        ; 
  471. Code    Ends
  472.     End
  473.  
  474.