home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / crypl200.zip / IDEA / IDEA8086.ASM < prev   
Assembly Source File  |  1995-06-21  |  10KB  |  286 lines
  1. ;A while ago I posted a message claiming a speed of 238,000
  2. ;bytes/sec for an implementation of IDEA on a 33Mh 486.  Below is
  3. ;an explanation and some code to show how it works.  The basic
  4. ;trick should be useful on many (but not all) processors.  I
  5. ;expect only those familiar with IDEA and its reference
  6. ;implementation will be able to follow the discussion.  See:
  7. ;
  8. ;Lai, Xueja and Massey, James L.  A Proposal for a New Block
  9. ;Encryption Standard, Eurocrypt 90
  10. ;
  11. ;For those who have been asking for the code, sorry I kept
  12. ;putting it off.  I wanted to get it out of Turbo Pascal
  13. ;ideal-mode, but I never had the time.
  14. ;
  15. ;Colin Plum wrote IDEA-386 code which is included in PGP
  16. ;2.3a and uses the same tricks.  I don't know who's is
  17. ;faster, but I expect they will be very close.  Now
  18. ;here's how it's done.
  19. ;
  20. ;A major bottleneck in software IDEA is the mul() routine, which
  21. ;is used 34 times per 64 bit block.  The routine performs
  22. ;multiplication in the multiplicative group mod 2^16+1.  The two
  23. ;factors are each in a 16 bit word, and the output is also in a 16
  24. ;bit word.  Note that 0 is not a member of the multiplicative
  25. ;group and 2^16 does not fit in 16 bits. We therefor use the 0
  26. ;word to represent 2^16.  Now group elements map one to one onto
  27. ;all possible 16 bit words, since 2^16+1 is prime.
  28. ;
  29. ;Here is (essentially) the reference implementation from [Lai].
  30. ;
  31. ;
  32. ;unsigned mul( unsigned a, unsigned b ) {
  33. ;  long int p ;
  34. ;  long unsigned q ;
  35. ;    if( a==0 ) p= 0x00010001 - b ;
  36. ;    else if( b==0 ) p= 0x00010001 - a ;
  37. ;    else {
  38. ;        q= a*b;
  39. ;        p= (q & 0xffff) - (q>>16)
  40. ;        if( p<0 ) p= p + 0x00010001 ;
  41. ;      }
  42. ;    return (unsigned)(p & 0xffff) ;
  43. ;}
  44. ;
  45. ;
  46. ;Note the method of reducing a 32 bit word modulo 2^16-1.  We
  47. ;subtract the high word from the low word, and add the modulus
  48. ;back if the result is less than 0.  [Lai] contains a proof that
  49. ;this works, and you can convince yourself fairly easily.
  50. ;
  51. ;To speed up this routine, we note that the tests for a=0 and b=0
  52. ;will rarely be false.  With the possible exception of the first 2
  53. ;of the 34 multiplications, 0 should be no more likely than any of
  54. ;the other 65535 numbers.  Note that if (and only if) either a or
  55. ;b is 0 then q will also be 0, and we can check for this in one
  56. ;instruction if our processor sets a zero flag for multiplication
  57. ;(as the 68000 does but 80x86 does not).
  58. ;
  59. ;Fortunately p will also be zero after the subtraction if and only
  60. ;if either a or b is 0.  Proof: r will be zero when the high order
  61. ;word of q equals the low order word, and that happens when q is
  62. ;divisible by 00010001 hex.  Since 00010001h = 2^16+1 is prime,
  63. ;this happens if either a or b is a multiple of 2^16+1, and 0 is
  64. ;the only such multiple which will fit in a 16 bit word.
  65. ;
  66. ;The speed-up strategy is to proceed under the assumption that a
  67. ;and b are not 0, check to be sure in one instruction, and
  68. ;recompute if the assumption was wrong.  Here's some 8086
  69. ;assembler code:
  70. ;
  71. ;    mov  ax, [a]
  72. ;    mul  [b]        ; ax is implied. q is now in DX AX
  73. ;    sub  ax, dx     ; mod 2^16+1
  74. ;    jnz  not0       ; Jump if neither op was 0. Usually taken.
  75. ;
  76. ;    mov  ax, 1      ; recompute result knowing one op is 0.
  77. ;    sub  ax, [a]
  78. ;    sub  ax, [b]
  79. ;    jmp  out        ; Just jump over adding the carry.
  80. ;not0:
  81. ;    adc  ax, 0      ; If r<0 add 1, otherwise do nothing.
  82. ;out:                ; Result is now in ax
  83. ;
  84. ;
  85. ;Note that when r<0 we add 1 instead of 2^16+1 since the 2^16 part
  86. ;overflows out of the result.  The "adc  ax, 0" does all the work
  87. ;of checking for a negative result and adding the modulus if
  88. ;needed.
  89. ;
  90. ;The multiplication takes 9 instructions, 4 of which are rarely
  91. ;executed.  I believe similar tricks are possible on many
  92. ;processors.  The one drawback to the check-after-multiply tactic
  93. ;is that we can't let the multiply overwrite the only copy of an
  94. ;operand.
  95. ;
  96. ;Note that most software implementations of IDEA will run at
  97. ;slightly different speeds when 0's come up in the multiply
  98. ;routine.  The reference implementation is faster on 0, this one
  99. ;is faster on non-zero.  This may be a problem for some real-time
  100. ;stuff, and also suggests an attack based on timing.
  101. ;
  102. ;Finally, below is an implementation of the complete encryption
  103. ;function in 8086 assembler, to replace the cipher_idea() function
  104. ;in PGP.  It takes the same parameters as the function from PGP,
  105. ;and uses the c language calling conventions.  I tested it using
  106. ;the debug features of the idea.c file in PGP.  You will need to
  107. ;add segment/assume directives.  This version uses no global data
  108. ;and should be reentrant.
  109. ;
  110. ;The handling of zero multipliers is outside the inner loop so
  111. ;that a short conditional jump can loop back to the beginning.
  112. ;Forward conditional jumps are usually not taken and backward
  113. ;jumps are usually taken, which is consistent with 586 branch
  114. ;prediction (or so I've heard).  Stalls where the output of one
  115. ;instruction is needed for the next seem unavoidable.
  116. ;
  117. ;Last I heard, IDEA was patent pending.  My code is up for grabs,
  118. ;although I would get a kick out being credited if you use it.
  119. ;On the other hand Colin's code is already tested and ready
  120. ;to assemble and link with PGP.
  121. ;
  122. ;--Bryan
  123. ;
  124. ;____________________CODE STARTS BELOW THIS LINE_________
  125.  
  126. ;  Called as: asmcrypt( inbuff, outbuff, zkey ) just like PGP
  127.  
  128. PROC    _asmcrypt
  129.  
  130.         ; establish parameter and local space on stack
  131.         ; follow c language calling conventions
  132.  
  133.         ARG  inblock:Word, outblock:Word, zkey:Word
  134.         LOCAL sx1:Word,sx4:Word,skk:Word,done8:Word =stacksize
  135.  
  136.         push bp
  137.         mov  bp, sp
  138.         sub  sp, stacksize
  139.  
  140.  ;      push ax     ; My compiler assumes these are not saved.
  141.  ;      push bx
  142.  ;      push cx
  143.  ;      push dx
  144.  
  145.         push si
  146.         push di
  147.  
  148. ; Put the 16 bit sub-blocks in registers and/or local variables
  149.         mov  si, [inblock]
  150.         mov  ax, [si]
  151.         mov  [sx1], ax       ; x1  is in ax and sx1
  152.         mov  di, [si+2]      ; x2  is in di
  153.         mov  bx, [si+4]      ; x3  is in bx
  154.         mov  dx, [si+6]
  155.         mov  [sx4], dx       ; x4  is in sx4
  156.  
  157.         mov  si, [zkey]      ; si points to next subkey
  158.         mov  [done8], si
  159.         add  [done8], 96     ; we will be finished with 8 rounds
  160.                              ; when si=done8
  161.  
  162. @@loop:                      ; 8 rounds of this
  163.         add  di, [si+2]      ; x2+=zkey[2]  is in di
  164.         add  bx, [si+4]      ; x3+=zkey[4]  is in bx
  165.  
  166.         mul  [Word si]       ;x1 *= zkey[0]
  167.         sub  ax, dx
  168.         jz  @@x1             ; if 0, use special case multiply
  169.         adc  ax, 0
  170. @@x1out:
  171.         mov  [sx1], ax       ; x1 is in ax and sx1
  172.  
  173.         xor  ax, bx          ; ax= x1^x3
  174.         mul  [Word si+8]     ; compute kk
  175.         sub  ax, dx          ; if 0, use special case multiply
  176.         jz  @@kk
  177.         adc  ax, 0
  178. @@kkout:
  179.         mov  cx, ax          ; kk is in cx
  180.  
  181.         mov  ax, [sx4]       ; x4 *= zkey[6]
  182.         mul  [Word si+6]
  183.         sub  ax, dx
  184.         jz   @@x4            ; if 0, use special case multiply
  185.         adc  ax, 0
  186. @@x4out:
  187.         mov  [sx4], ax       ; x4 is in sx4 and ax
  188.  
  189.         xor  ax, di          ; x4^x2
  190.         add  ax, cx          ; kk+(x2^x4)
  191.         mul  [Word si+10]    ; compute t1
  192.         sub  ax, dx
  193.         jz  @@t1             ; if 0, use special case multiply
  194.         adc  ax, 0
  195. @@t1out:                     ; t1 is in ax
  196.  
  197.         add  cx, ax          ; t2 is in cx   kk+t1
  198.  
  199.         xor  [sx4], cx       ; x4 in sx4
  200.         xor  di, cx          ; new x3 in di
  201.         xor  bx, ax          ; new x2 in bx
  202.         xchg bx, di          ; x2 in di, x3 in bx
  203.         xor  ax, [sx1]       ; x1 in ax
  204.         mov  [sx1], ax       ; and [sx1]
  205.  
  206.         add  si, 12          ; point to next subkey
  207.         cmp  si, [done8]
  208.         jne  @@loop
  209.         jmp  @@out8
  210.  
  211. ;------------------------------------------
  212. ; Special case multiplications, when one factor is 0
  213.  
  214. @@x1:   mov  ax, 1
  215.         sub  ax, [sx1]
  216.         sub  ax, [Word si]
  217.         jmp  @@x1out
  218.  
  219. @@kk:   mov  ax, [sx1]       ; rebuild overwritten operand
  220.         xor  ax, bx
  221.         neg  ax
  222.         inc  ax
  223.         sub  ax, [si+8]
  224.         jmp  @@kkout
  225.  
  226. @@x4:   mov  ax, 1
  227.         sub  ax, [sx4]
  228.         sub  ax, [Word si+6]
  229.         jmp  @@x4out
  230.  
  231. @@t1:   mov  ax, [sx4]       ; rebuild
  232.         xor  ax, di
  233.         add  ax, cx
  234.         neg  ax
  235.         inc  ax
  236.         sub  ax, [si+10]
  237.         jmp  @@t1out
  238.  
  239. ;---------------------------------------------------
  240. ;   8 rounds are done, now that extra pseudo-round
  241.  
  242. @@out8:
  243.         push di
  244.         mov  di, [outblock]
  245.  
  246.         mul  [Word si]
  247.         sub  ax, dx
  248.         jnz  @@o1n           ; jump over special case code
  249.         mov  ax, 1
  250.         sub  ax, [sx1]
  251.         sub  ax, [si]
  252.         jmp  @@o1out
  253. @@o1n:  adc  ax, 0
  254. @@o1out:  mov [di], ax       ; final ciphertext block 1
  255.  
  256.         mov  ax, [sx4]
  257.         mul  [Word si+6]
  258.         sub  ax, dx
  259.         jnz  @@o4n           ; jump over special case code
  260.         mov  ax, 1
  261.         sub  ax, [sx4]
  262.         sub  ax, [si+6]
  263.         jmp  @@o4out
  264. @@o4n:  adc  ax, 0
  265. @@o4out: mov  [di+6], ax     ; final ciphertext block 4
  266.  
  267.         add  bx, [si+2]
  268.         mov  [di+2], bx      ; final ciphertext block 2
  269.         pop  ax
  270.         add  ax, [si+4]
  271.         mov  [di+4], ax      ; final ciphertext block 3
  272.  
  273. ;  Restore the stack and return
  274.  
  275.         pop  di
  276.         pop  si
  277. ;       pop  dx
  278. ;       pop  cx
  279. ;       pop  bx
  280. ;       pop  ax
  281.  
  282.         mov  sp, bp
  283.         pop  bp
  284.         ret
  285. ENDP    _asmcrypt
  286.