host/gcdext-test.rb

   1 #!/usr/bin/ruby
   2 # gcdext-test.rb
   3 =begin
   4     This file is part of the ARM-Crypto-Lib.
   5     Copyright (C) 2008, 2009  Daniel Otte (daniel.otte@rub.de)
   6
   7     This program is free software: you can redistribute it and/or modify
   8     it under the terms of the GNU General Public License as published by
   9     the Free Software Foundation, either version 3 of the License, or
  10     (at your option) any later version.
  11
  12     This program is distributed in the hope that it will be useful,
  13     but WITHOUT ANY WARRANTY; without even the implied warranty of
  14     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15     GNU General Public License for more details.
  16
  17     You should have received a copy of the GNU General Public License
  18     along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19 =end
  20
  21 $debug = true
  22 $debug = false
  23 require 'rubygems'
  24 require 'serialport'
  25 require 'getopt/std'
  26 require 'ftools'
  27 require 'date'
  28
  29 def gcdext(x,y)
  30   g=1
  31   i=0
  32   while(x&1==0 && y&1==0) do
  33     x>>=1
  34     y>>=1
  35     g<<=1
  36     i+=1
  37   end
  38   printf("DBG: initshift = %04X\n", i)
  39   u=x; v=y; a=1; b=0; c=0; d=1
  40   begin
  41     printf(" while u%%2==0; u = %X\n", u)
  42     printf("DBG: (10) a = %s\n", a.to_s(16).upcase)
  43     printf("DBG: (10) b = %s\n", b.to_s(16).upcase)
  44     printf("DBG: (10) c = %s\n", c.to_s(16).upcase)
  45     printf("DBG: (10) d = %s\n", d.to_s(16).upcase)
  46     while(u&1==0) do
  47       if(a%2==1 || b%2==1)
  48         a += y
  49         b -= x
  50       end
  51       u>>=1; a>>=1; b>>=1
  52     end
  53     printf(" while v%%2==0; v = %X\n", v)
  54     printf("DBG: (20) a = %s\n", a.to_s(16).upcase)
  55     printf("DBG: (20) b = %s\n", b.to_s(16).upcase)
  56     printf("DBG: (20) c = %s\n", c.to_s(16).upcase)
  57     printf("DBG: (20) d = %s\n", d.to_s(16).upcase)
  58     while(v&1==0) do
  59       if(c%2==1 || d%2==1)
  60         c += y
  61     #    printf("DBG: (qq) b = %s\n", b.to_s(16).upcase)
  62         d -= x
  63       end
  64       printf("DBG: (xx) d = %s\n", d.to_s(16).upcase)
  65       v>>=1; c>>=1; d>>=1;
  66     end
  67
  68     printf(" if u>=v ...\n")
  69     printf("DBG: (30) a = %s\n", a.to_s(16).upcase)
  70     printf("DBG: (30) b = %s\n", b.to_s(16).upcase)
  71     printf("DBG: (30) c = %s\n", c.to_s(16).upcase)
  72     printf("DBG: (30) d = %s\n", d.to_s(16).upcase)
  73
  74     if(u>=v)
  75       u -= v; a-=c; b-=d
  76     else
  77       v -= u; c-=a; d-=b
  78     end
  79   end while(u!=0)
  80   return[g*v, c, d]
  81 end
  82
  83
  84 if ARGV.length==2
  85   a = ARGV[0].to_i
  86   b = ARGV[1].to_i
  87 else
  88   # CD319349, 9EFD76CC
  89   # 1609000771, 6fac577d72
  90   a = 0x1609000771
  91   b = 0x6fac577d72
  92 end
  93 r = gcdext(a, b)
  94 printf("gcdext( %s, %s) => a = %s; b = %s; gcd = %s\n",
  95   a.to_s(16),b.to_s(16),r[1].to_s(16),r[2].to_s(16),r[0].to_s(16))
  96
  97