PureBoard

Das deutsche PureBasic-Forum
https://www.purebasic.fr/german/

natural numbers zum RSA rechen...

https://www.purebasic.fr/german/viewtopic.php?t=5448

Seite 1 von 1

natural numbers zum RSA rechen...

Verfasst: 02.11.2005 23:50
von andi256
So .. mir war mal langweilig und hab zum RSA rechen die

natural numbers von
Copyright (C) RSA Laboratories, a division of RSA Data Security,
Inc., created 1991. All rights reserved.
ins PB übersetzt

quelle
:http://cvs.sourceforge.net/viewcvs.py/w ... _orig/rsa/

vielleicht kanns wer brauchen bzw. hat ein paar verbesserungsvorschläge / anregungen

werde die anderen RSA Funktionen auch schön langsam mal inkludieren ...

PS:
Diese Source dient zum Rechen beliebig grosser Zahlen .. (zb. RSA)
eine Zahl mit mit 100 Nullen hoch einer Zahl mit 100 Nullen mod einer Zahl mit 100 Nullen bis auf die letzte Stelle :mrgreen:
NN_ModExp (*a.LNG,*b.LNG,*c.LNG,cDigits,*d.LNG,dDigits)
a = b^c mod d

Source ist noch nicht 100% getestet aber vorab:

Code: Alles auswählen

; N O T E : !!!!!!
;Copyright (C) RSA Laboratories, a division of RSA Data Security, 
;Inc., created 1991. All rights reserved.

; Constants

;Note: MAX_NN_DIGITS is long enough To hold any RSA modulus, plus
;one more digit as required by R_GeneratePEMKeys (For n And phiN,
;whose lengths must be even). All natural numbers have at most
;MAX_NN_DIGITS digits, except For double-length intermediate values
;in NN_Mult (t), NN_ModMult (t), NN_ModInv (w), And NN_Div (c).

;RSA key lengths. 
#MIN_RSA_MODULUS_BITS   =1024
#MAX_RSA_MODULUS_BITS   =4096
#MAX_RSA_MODULUS_LEN    =((#MAX_RSA_MODULUS_BITS + 7) / 8)
#MAX_RSA_PRIME_BITS     =((#MAX_RSA_MODULUS_BITS + 1) / 2)
#MAX_RSA_PRIME_LEN      =((#MAX_RSA_PRIME_BITS   + 7) / 8)

;Length of digit in bits 
#NN_DIGIT_BITS         =32
#NN_HALF_DIGIT_BITS    =16
;Length of digit in bytes
#NN_DIGIT_LEN          =(#NN_DIGIT_BITS / 8)
;Maximum length in digits 
#MAX_NN_DIGITS         =((#MAX_RSA_MODULUS_LEN + #NN_DIGIT_LEN - 1) / #NN_DIGIT_LEN + 1)
;Maximum digits 
#MAX_NN_DIGIT          = $ffffffff
#MAX_NN_HALF_DIGIT     = $ffff

Structure LNG
 l.l[#MAX_NN_DIGITS ]
EndStructure 

Structure LNG_3
 lng.LNG[3]
EndStructure 

;CONVERSIONS
;Declare NN_Decode       (a, digits, b, len   )                        ;Decodes character string b into a.
;Declare NN_Encode       (a, len,    b, digits)                        ;Encodes a into character string b.
;ASSIGNMENTS
Declare NN_Assign       (*a.LNG, *b.LNG, digits)                      ;Assigns a = b.
Declare NN_Assign_digit (*a.LNG,  b,     digits)                      ;Assigns a = b, where b is a digit.
Declare NN_AssignZero   (*a.LNG,         digits)                      ;Assigns a = 0.
Declare NN_Assign2Exp   (*a.LNG,  b,     digits)                      ;Assigns a = 2^b.
;ARITHMETIC OPERATIONS
Declare NN_Add          (*a.LNG,*b.LNG,*c.LNG, digits)                ;Computes a = b + c.
Declare NN_Sub          (*a.LNG,*b.LNG,*c.LNG, digits)                ;Computes a = b - c.
Declare NN_Mult         (*a.LNG,*b.LNG,*c.LNG, digits)                ;Computes a = b * c.
Declare NN_LShift       (*a.LNG,*b.LNG, c,     digits)                ;Computes a = b * 2^c.
Declare NN_RShift       (*a.LNG,*b.LNG, c,     digits)                ;Computes a = b / 2^c.
Declare NN_Div          (*a.LNG,*b.LNG,*c.LNG,cDigits,*d.LNG,ddigits) ;Computes a = c div d And b = c mod d.
;NUMBER THEORY
Declare NN_Mod          (*a.LNG,*b.LNG,bDigits,*c.LNG,cdigits)        ;Computes a = b mod c.
Declare NN_ModMult      (*a.LNG,*b.LNG,*c.LNG,*d.LNG,digits)          ;Computes a = b * c mod d.
Declare NN_ModExp       (*a.LNG,*b.LNG,*c.LNG,cdigits,*d.LNG,ddigits) ;Computes a = b^c mod d.
Declare NN_ModInv       (*a.LNG,*b.LNG,*c.LNG,digits)                 ;Computes a = 1/b mod c.
Declare NN_Gcd          (*a.LNG,*b.LNG,*c.LNG,digits)                 ;Computes a = gcd (b, c).
;OTHER OPERATIONS
Declare NN_EVEN         (*a.LNG,digits)                               ;Returns 1 if a is even.
Declare NN_Cmp          (*a.LNG,*b.LNG,digits)                        ;Returns sign of a - b.
Declare NN_EQUAL        (*a.LNG,*b.LNG,digits)                        ;Returns 1 if a = b.
Declare NN_Zero         (*a.LNG,digits)                               ;Returns 1 if a = 0.
Declare NN_Digits       (*a.LNG,digits)                               ;Returns significant length of a in digits.
Declare NN_Bits         (*a.LNG,digits)                               ;Returns significant length of a in bits.

Procedure groesser(a,b) 
 !XOR eax,eax 
 !MOV ebx,[esp] 
 !CMP ebx,[esp+4] 
 !SETA al 
 ProcedureReturn 
EndProcedure

Procedure groessergleich(a,b) 
 !XOR eax,eax 
 !MOV ebx,[esp] 
 !CMP ebx,[esp+4] 
 !SETAE al 
 ProcedureReturn 
EndProcedure 

Procedure div(a,b) 
 !MOV eax,[esp]           
 !XOR edx,edx             
 !DIV dword [esp+4]       
 ProcedureReturn        
EndProcedure 

Procedure LOW_HALF(x) 
 ProcedureReturn x&#MAX_NN_HALF_DIGIT
EndProcedure

Procedure HIGH_HALF(x)
 ProcedureReturn (x>>#NN_HALF_DIGIT_BITS)&#MAX_NN_HALF_DIGIT
EndProcedure

Procedure TO_HIGH_HALF(x) 
 ProcedureReturn x<<#NN_HALF_DIGIT_BITS
EndProcedure 

Procedure DIGIT_MSB(x) 
 ProcedureReturn (x>>(#NN_DIGIT_BITS-1))&1
EndProcedure 

Procedure DIGIT_2MSB(x) 
 ProcedureReturn (x>>(#NN_DIGIT_BITS-2))&3
EndProcedure 

Procedure NN_ASSIGN_DIGIT(*a.LNG,b,digits) 
 NN_AssignZero (*a,digits)
 *a\l[0]=b
EndProcedure

Procedure NN_EQUAL(*a.LNG,*b.LNG,digits) 
 ProcedureReturn = ~NN_Cmp(*a,*b,digits)
EndProcedure

Procedure NN_EVEN(*a.LNG,digits) 
; (((digits) == 0) || ! (a[0] & 1))
EndProcedure

;Returns nonzero if a is zero.
;Lengths: a[digits].
Procedure NN_Zero(*a.LNG,digits) 
 For i=0 To digits
 If *a\l[i]
  ProcedureReturn 0
 EndIf   
 Next i
 ProcedureReturn 1
EndProcedure

;MSB -> LSB
Procedure NN_DecodeLE(*a.LNG,*b.lng,len)
 For i=0 To len-1
  PokeB(*a+len-i-1,PeekB(*b+i))
 Next i 
EndProcedure

;LSB -> MSB
Procedure NN_EncodeLE(*a.LNG,*b.lng,len)
 For i=0 To len-1
  PokeB(*a+len-i-1,PeekB(*b+i))
 Next i 
EndProcedure

;Returns the significant length of a in bits, where a is a digit
Procedure NN_DigitBits(a)  
 While a<>0 And i<#NN_DIGIT_BITS 
  i+1
  a=a>>1
 Wend
 ProcedureReturn i
EndProcedure 

;Returns the significant length of a in digits.
;Lengths: a[digits]
Procedure NN_Digits(*a.LNG,digits)
 digits-1
 While (digits>=0) And *a\l[digits]=0 
  digits-1
 Wend
 ProcedureReturn digits+1
EndProcedure

;Returns the significant length of a in bits.
;Lengths: a[digits]
Procedure NN_Bits (*a.LNG,digits)
 digits=NN_Digits(*a.LNG,digits)
 If digits=0
  ProcedureReturn 0
 EndIf 
 a=(digits-1)*#NN_DIGIT_BITS+NN_DigitBits(*a\l[digits-1])
 ProcedureReturn a
EndProcedure

;Assigns a = 0.
;Lengths: a[digits].
Procedure NN_AssignZero(*a.LNG,digits)
 For i=0 To digits-1
  *a\l[i]=0
 Next i 
EndProcedure

;Assigns a = b.
;Lengths: a[digits], b[digits]
Procedure NN_Assign(*a.LNG,*b.LNG,digits)
 For i=0 To digits-1
  *a\l[i]=*b\l[i]
 Next i  
EndProcedure

;Assigns a = 2^b.
;Lengths: a[digits].
;Requires b < digits * NN_DIGIT_BITS
Procedure NN_Assign2Exp (*a.LNG,b,digits)
 NN_AssignZero(*a,digits)
 If (b>=digits*#NN_DIGIT_BITS)
  ProcedureReturn;
 EndIf   
 *a\l[b/#NN_DIGIT_BITS]=1<<(b%#NN_DIGIT_BITS)
EndProcedure

;Computes a = b * 2^c (i.e., shifts left c bits), returning carry.
;Lengths: a[digits], b[digits].
;Requires c < NN_DIGIT_BITS.
Procedure NN_LShift(*a.LNG,*b.LNG,c,digits)
 t=#NN_DIGIT_BITS-c
 i=digits
 If t<=0 
  ProcedureReturn 0
 EndIf
 If c
  bc=0:ac=0
  While i
   i-1
   dummy=*b\l[bc]
   bc+1
   *a\l[ac]=(dummy<<c)|carry
   ac+1
   carry=dummy>>t&Val(Str((Pow(2,c))-1));????
  Wend
 Else 
  NN_Assign (*a.LNG,*b.LNG,digits)
 EndIf 
 ProcedureReturn carry
EndProcedure

;Computes a = b * 2^c (i.e., shifts left c bits), returning carry.
;Lengths: a[digits], b[digits].
;Requires c < NN_DIGIT_BITS. */
Procedure NN_RShift(*a.LNG,*b.LNG,c,digits)
 t=#NN_DIGIT_BITS-c
 i=digits
 If t<=0 
  ProcedureReturn 0
 EndIf
 If c
  bc+i-1:ac+i-1
  While i
   i-1
   dummy=*b\l[bc]
   bc-1
   *a\l[ac]=((dummy>>c)&Val(Str((Pow(2,t))-1)))|carry
   ac-1
   carry=dummy<<t;&Val(Str((Pow(2,c))-1));????
  ; Debug "carry"+Hex(carry)+" " +Str(i)
  Wend
 Else 
  NN_Assign(*a.LNG,*b.LNG,digits)
 EndIf 
 ProcedureReturn carry
EndProcedure

;Computes a = b + c. Returns carry.
;Lengths: a[digits], b[digits], c[digits]
Procedure NN_Add(*a.LNG,*b.LNG,*c.LNG,digits)
 bc=0:cc=0:ac=0
 carry=0
 While digits>0
  digits-1
  ai=*b\l[bc]+carry
  bc+1
  If ai<carry
   ai=*c\l[cc]
   cc+1
  Else 
   ai=ai+*c\l[cc]
   If groesser(*c\l[cc],ai)
    carry=#true
   Else 
    carry=#false
   EndIf
   cc+1 
  EndIf  
  *a\l[ac]=ai
  ac+1
 Wend  
 ProcedureReturn carry
EndProcedure

;Computes a = b - c. Returns borrow.
;Lengths: a[digits], b[digits], c[digits]
Procedure NN_Sub(*a.LNG,*b.LNG,*c.LNG,digits)
 ac=0:bc=0:cc=0
 While digits>0
  digits-1
  ai=*b\l[bc]-borrow
  bc+1
  If groesser(ai,(#MAX_NN_DIGIT-borrow))
   ai=#MAX_NN_DIGIT-*c\l[cc]
  Else 
   ai=ai-*c\l[cc]
   If groesser(ai,(#MAX_NN_DIGIT-*c\l[cc]))
    borrow=#true
   Else
    borrow=#false
   EndIf
   cc+1
  EndIf
  *a\l[ac]=ai
  ac+1
 Wend
 ProcedureReturn borrow
EndProcedure

Procedure NN_DigitMult(*a.lng,b,c)
 bHigh=HIGH_HALF(b)
 bLow =LOW_HALF(b)
 cHigh=HIGH_HALF(c)
 cLow =LOW_HALF(c)
 *a\l[0]=bLow *cLow
 t      =bLow *cHigh
 u      =bHigh*cLow
 *a\l[1]=bHigh*cHigh
 t=t+u
 If groesser(u,t)
  *a\l[1]=*a\l[1]+TO_HIGH_HALF(1)
 EndIf
 u=TO_HIGH_HALF (t)
 *a\l[0]=*a\l[0]+u
 If groesser(u,*a\l[0])
  *a\l[1]+1 
 EndIf
 *a\l[1]+HIGH_HALF(t) 
EndProcedure

;Computes a = b + c*d, where c is a digit. Returns carry.
;Lengths: a[digits], b[digits], d[digits].
Procedure NN_AddDigitMult (*a.LNG,*b.LNG,c,*d.LNG,digits)
 *t.lng =AllocateMemory(8)
 If c=0
  ProcedureReturn 0
 EndIf 
 carry = 0
 i = digits
 dc=0:bc=0:ac=0
 While i
  i-1 
  NN_DigitMult(*t, c, *d\l[dc])
  dc+1
  *a\l[ac]=*b\l[bc]+carry
  bc+1
  If groesser(carry,*a\l[ac])
   carry=#TRUE
  Else
   carry=#FALSE
  EndIf  
  *a\l[ac] + *t\l[0]
  If groesser(*t\l[0],*a\l[ac])
   carry+1+*t\l[1]
  Else
   carry+*t\l[1]
  EndIf 
  ac+1
 Wend
 ProcedureReturn carry
EndProcedure

;Computes a = b * c.
;Lengths: a[2*digits], b[digits], c[digits].
;Assumes digits < MAX_NN_DIGITS.
Procedure NN_Mult(*a.LNG,*b.LNG,*c.LNG,digits)
 *t.Lng=AllocateMemory(2*#MAX_NN_DIGITS)
 NN_AssignZero (*t,2*digits)
 bDigits=NN_Digits (*b,digits)
 cDigits=NN_Digits (*c,digits)
 For i=0 To bDigits-1     
  dummy=NN_AddDigitMult(@*t\l[i],@*t\l[i],*b\l[i],*c,cDigits)
  *t\l[i+cDigits]+dummy
 Next i
 NN_Assign (*a,*t,2*digits)
EndProcedure

;Sets a = b / c, where a And c are digits.
;Lengths: b[2]
;Assumes b[1] < c And HIGH_HALF (c) > 0. For efficiency, c should be normalized.
Procedure NN_DigitDiv (*a.lng,*b.lng,*c.lng)
 *t.Lng=AllocateMemory(8)
 cHigh=HIGH_HALF(*c\l[0])
 cLow=LOW_HALF(*c\l[0])
 *t\l[0]=*b\l[0]
 *t\l[1]=*b\l[1]
 If cHigh=#MAX_NN_HALF_DIGIT
  aHigh=HIGH_HALF(*t\l[1])
 Else
  aHigh=(*t\l[1]/(cHigh + 1))
 EndIf  
 u=aHigh*cLow
 v=aHigh*cHigh
 *t\l[0]=*t\l[0]-TO_HIGH_HALF(u)
 If groesser(*t\l[0],(#MAX_NN_DIGIT-TO_HIGH_HALF(u)))
  *t\l[1]-1
 EndIf  
 *t\l[1]=*t\l[1]-(HIGH_HALF(u))
 *t\l[1]=*t\l[1]-v
 While groesser(*t\l[1],cHigh) Or ((*t\l[1]=cHigh) And groessergleich(*t\l[0],TO_HIGH_HALF(cLow)))
  *t\l[0]=*t\l[0]-TO_HIGH_HALF(cLow)
  If groesser(*t\l[0],#MAX_NN_DIGIT-TO_HIGH_HALF(cLow))
   *t\l[1]-1
  EndIf  
  *t\l[1]=*t\l[1]-cHigh
  aHigh+1
 Wend
 If cHigh=#MAX_NN_HALF_DIGIT
  aLow=LOW_HALF(*t\l[1])
 Else
 aLow=div(TO_HIGH_HALF(*t\l[1])+HIGH_HALF(*t\l[0]),cHigh+1)
 EndIf
 u=aLow*cLow
 v=aLow*cHigh
 *t\l[0]=*t\l[0]-u
 If groesser(*t\l[0],#MAX_NN_DIGIT-u)
  *t\l[1]-1
 EndIf 
 *t\l[0]-TO_HIGH_HALF (v)
 If groesser(*t\l[0],(#MAX_NN_DIGIT-TO_HIGH_HALF(v)))
  *t\l[1]-1
 EndIf  
 *t\l[1]=*t\l[1]-HIGH_HALF(v)
 While groesser(*t\l[1],0) Or ((*t\l[1]=0) And groessergleich(*t\l[0],*c\l[0]))
  *t\l[0]-*c\l[0]
   If groesser(*t\l[0],#MAX_NN_DIGIT-*c\l[0])
   *t\l[1]-1
  EndIf  
  aLow+1
 Wend
 FreeMemory(*t)
 *a\l[0]=TO_HIGH_HALF (aHigh) + aLow
EndProcedure

;Returns sign of a - b.
;Lengths: a[digits], b[digits]. */
Procedure NN_Cmp (*a.lng, *b.lng, digits)
 For i=digits-1 To 0 step-1
  If groesser(*a\l[i],*b\l[i])
   ProcedureReturn 1
  EndIf 
  If groesser(*b\l[i],*a\l[i])
   ProcedureReturn -1
  EndIf
 Next i
 ProcedureReturn 0
EndProcedure

;Computes a = b - c*d, where c is a digit. Returns borrow.
;Lengths: a[digits], b[digits], d[digits]. */
Procedure NN_SubDigitMult (*a.LNG, *b.LNG, c, *d.LNG, digits)
  *t.LNG = AllocateMemory(8)
  i=digits
  If c=0
   ProcedureReturn 0
  EndIf 
  ddc=0:bbc=0
  While i
   i-1
   NN_DigitMult(*t,c,*d\l[ddc])
   ddc+1 
   *a\l[aac]=*b\l[bbc]-borrow
   borrow=groesser(*a\l[aac], #MAX_NN_DIGIT-borrow)
   bbc+1
   *a\l[aac]-*t\l[0]
   borrow+groesser(*a\l[aac],(#MAX_NN_DIGIT-*t\l[0]))+*t\l[1]
   aac+1 
  Wend
 ProcedureReturn borrow
EndProcedure

;Computes a = b mod c.
;Lengths: a[cDigits], b[bDigits], c[cDigits].
;Assumes c > 0, bDigits < 2 * MAX_NN_DIGITS, cDigits < MAX_NN_DIGITS. 
Procedure NN_Mod (*a.LNG,*b.LNG,bDigits,*c.LNG,cDigits)
 *t.LNG= AllocateMemory((2*#MAX_NN_DIGITS+1)*4) 
 NN_Div (*t, *a, *b,bDigits,*c,cDigits)
 ;Zeroize potentially sensitive information.  
 FreeMemory(*t)
EndProcedure

;Computes a = b * c mod d.
;Lengths: a[digits], b[digits], c[digits], d[digits].
;Assumes d > 0, digits < MAX_NN_DIGITS.
Procedure NN_ModMult(*a.LNG,*b.LNG,*c.LNG,*d.LNG,digits)
 *t.LNG=AllocateMemory((2*#MAX_NN_DIGITS+1)*4) 
 NN_Mult(*t,*b,*c,digits)
 NN_Mod(*a,*t,2 * digits,*d,digits)
 ;Zeroize potentially sensitive information.  
 FreeMemory(*t)
EndProcedure

;Computes a = b^c mod d.
;Lengths: a[dDigits], b[dDigits], c[cDigits], d[dDigits].
;Assumes d > 0, cDigits > 0, dDigits < MAX_NN_DIGITS. */
Procedure NN_ModExp (*a.LNG,*b.LNG,*c.LNG,cDigits,*d.LNG,dDigits)
 *bPower.LNG_3= AllocateMemory(SizeOf(LNG_3))
 *t.LNG= AllocateMemory((2*#MAX_NN_DIGITS+1)*4) 
 ;Store b, b^2 mod d, And b^3 mod d.   
 NN_Assign (@*bPower\lng[0]\l,*b,dDigits)
 NN_ModMult(@*bPower\lng[1]\l,@*bPower\lng[0]\l,*b,*d,dDigits)
 NN_ModMult(@*bPower\lng[2]\l,@*bPower\lng[1]\l,*b,*d,dDigits)
 NN_ASSIGN_DIGIT (*t,1,dDigits)
 cDigits=NN_Digits (*c,cDigits)
 For i=cDigits-1 To 0 Step -1 
  ci=*c\l[i]
  ciBits=#NN_DIGIT_BITS
 ;Scan past leading zero bits of most significant digit.     
  If i=cDigits-1
   While DIGIT_2MSB (ci)=0 
    ci<<2
    ciBits-2
   Wend
  EndIf
  For j = 0 To ciBits-1 Step 2
   ;Compute t = t^4 * b^s mod d, where s = two MSB's of ci.       
   NN_ModMult(*t,*t,*t,*d,dDigits)
   NN_ModMult(*t,*t,*t,*d,dDigits)
   s=DIGIT_2MSB(ci)
   If s <>0
    NN_ModMult(*t,*t,@*bPower\lng[s-1]\l,*d,dDigits)
   EndIf  
   ci<<2
  Next j
 Next i
 NN_Assign(*a,*t,dDigits)
 ;Zeroize potentially sensitive information.   
 FreeMemory(*bPower)
 FreeMemory(*t)
EndProcedure

;Compute a = 1/b mod c, assuming inverse exists.
;Lengths: a[digits], b[digits], c[digits].
;Assumes gcd (b, c) = 1, digits < MAX_NN_DIGITS. 
Procedure NN_ModInv (*a.LNG,*b.LNG,*c.LNG, digits)
 *q.LNG =AllocateMemory((#MAX_NN_DIGITS+1)*4) 
 *t1.LNG=AllocateMemory((#MAX_NN_DIGITS+1)*4)   
 *t3.LNG=AllocateMemory((#MAX_NN_DIGITS+1)*4) 
 *u1.LNG=AllocateMemory((#MAX_NN_DIGITS+1)*4)
 *u3.LNG=AllocateMemory((#MAX_NN_DIGITS+1)*4) 
 *v1.LNG=AllocateMemory((#MAX_NN_DIGITS+1)*4) 
 *v3.LNG=AllocateMemory((#MAX_NN_DIGITS+1)*4) 
 *w.LNG =AllocateMemory((2*#MAX_NN_DIGITS+1)*4) 
 ;Apply extended Euclidean algorithm, modified To avoid negative   numbers.   
 NN_ASSIGN_DIGIT(*u1,1,digits)
 NN_AssignZero(*v1,digits)
 NN_Assign(*u3,*b,digits)
 NN_Assign(*v3,*c,digits)
 u1Sign = 1
 While (~ NN_Zero(*v3,digits)) 
  NN_Div   (*q,*t3,*u3,digits,*v3,digits)
  NN_Mult  (*w,*q,*v1,digits)
  NN_Add   (*t1,*u1,*w,digits)
  NN_Assign(*u1,*v1,digits)
  NN_Assign(*v1,*t1,digits)
  NN_Assign(*u3,*v3,digits)
  NN_Assign(*v3,*t3,digits)
  u1Sign = -u1Sign
 Wend
 ;Negate result If sign is negative.    
 If (u1Sign< 0)
  NN_Sub (*a,*c,*u1,digits)
 Else
  NN_Assign (*a,*u1,digits)
 EndIf  
 ;Zeroize potentially sensitive information.   
 FreeMemory(*q)
 FreeMemory(*t1)
 FreeMemory(*t3)
 FreeMemory(*u1)
 FreeMemory(*u3)
 FreeMemory(*v1)
 FreeMemory(*v3)
 FreeMemory(*w)
EndProcedure

;Computes a = c div d And b = c mod d.
;Lengths: a[cDigits], b[dDigits], c[cDigits], d[dDigits].
;Assumes  d > 0, cDigits < 2 * MAX_NN_DIGITS,dDigits < MAX_NN_DIGITS. 
Procedure NN_Div (*a.lng,*b.lng,*c.lng,cDigits,*d.lng,dDigits)
 *cc.LNG=AllocateMemory((2*#MAX_NN_DIGITS+1)*4) 
 *dd.LNG=AllocateMemory(#MAX_NN_DIGITS*4)
 ddDigits=NN_Digits(*d, dDigits)
 If ddDigits=0
  ProcedureReturn
 EndIf 
 ;Normalize operands
 shift=#NN_DIGIT_BITS-NN_DigitBits(*d\l[ddDigits-1])
 NN_AssignZero(*cc, ddDigits)
 *cc\l[cDigits]=NN_LShift(*cc,*c,shift,cDigits)
 NN_LShift (*dd,*d,shift,ddDigits)
 t=*dd\l[ddDigits-1]
 NN_AssignZero(*a,cDigits)
 For i=cDigits-ddDigits To 0 step-1 
  ;Underestimate quotient digit And subtract.     
  If t=#MAX_NN_DIGIT 
   ai=*cc\l[i+ddDigits]
  Else 
   k=t+1
   NN_DigitDiv (@ai,@*cc\l[i+ddDigits-1],@k)
  EndIf 
  *cc\l[i+ddDigits] -NN_SubDigitMult(@*cc\l[i],@*cc\l[i],ai,*dd, ddDigits) 
 ; Correct estimate.
  While (groesser(*cc\l[i+ddDigits],0)) Or (NN_Cmp (@*cc\l[i],*dd, ddDigits)>=0)
   ai+1
   *cc\l[i+ddDigits]-NN_Sub(@*cc\l[i],@*cc\l[i],*dd,ddDigits)
  Wend
  *a\l[i]=ai
 Next i
 ;Restore result.   
 NN_AssignZero(*b, dDigits)
 NN_RShift(*b,*cc, shift,ddDigits)
 ;Zeroize potentially sensitive information.   
 FreeMemory(*cc)
 FreeMemory(*dd)
EndProcedure

;Computes a = gcd(b, c).
;Lengths: a[digits], b[digits], c[digits].
;Assumes b > c, digits < MAX_NN_DIGITS.
Procedure NN_Gcd(*a.LNG,*b.LNG,*c.LNG,digits)
 *t=AllocateMemory(#MAX_NN_DIGITS*4)
 *u=AllocateMemory(#MAX_NN_DIGITS*4)
 *v=AllocateMemory(#MAX_NN_DIGITS*4)
 NN_Assign(*u,*b,digits)
 NN_Assign(*v,*c,digits)
 While NN_Zero(v, digits) <> 0
  NN_Mod(*t,*u,digits,*v,digits)
  NN_Assign(*u,*v,digits)
  NN_Assign(*v,*t,digits)
 Wend
 NN_Assign(*a,*u,digits)
 ;Zeroize potentially sensitive information.
 FreeMemory(*t)
 FreeMemory(*u)
 FreeMemory(*v)
EndProcedure
Andi256

Verfasst: 03.11.2005 08:39
von Kukulkan
Hi andi256,

Tolle Sache das... :allright:

Wirst Du die in rsa.h angegebenen Funktionen auch einbauen? Wäre ja super, weil die vor allem dann auch auf Linux zur Verfügung stehen würden und somit endlich auch diese Funktionen per PB Cross-Platform würden!

Gibt es irgendwo Examples zur Benutzung?

Ich benötige aktuell den Modul und eine Power-Funktion für grosse Zahlen. Mal sehen ob das mit diesem Code geht...

Volker

Verfasst: 03.11.2005 10:26
von andi256
Gibt es irgendwo Examples zur Benutzung

Code: Alles auswählen

; *********************** T E S T ****************************

Procedure UpeekB(*mem)
 ProcedureReturn Val(StrU(PeekB(*mem),#BYTE))
EndProcedure

Procedure.s speicherout_hex(*mem,l,q$)
 For i=0 To l-1
  q$=q$+RSet(Hex(UPeekB(*mem+i)),2,"0")+" "
 Next i
ProcedureReturn q$
EndProcedure

;Zahl1 = "12345678901234567890"
;Zahl2 = "123456789012345"
;Zahl3 = "987654321098765"

;Zahl1inhex = "AB 54 A9 8C EB 1F 0A D2"
;Zahl2inhex = "70 48 86 0D DF 79"
;Zahl3inhex = "03 82 44 30 F8 50 0D"

; Alle Funktionen rechen in little endian
; daher umwandeln in "little endian" LSB (LeastSignificantByte)
DataSection
Zahl1inhexLSB:
Data.b $D2,$0A,$1F,$EB,$8C,$A9,$54,$AB
; auffüllen mit Nullen (immer in 4er Blöcken (Longs) hier 8Byte entspricht 2xlongs 
Zahl2inhexLSB:
Data.b $79,$DF,$0D,$86,$48,$70,$00,$00
Zahl3inhexLSB:
Data.b $0D,$50,$F8,$30,$44,$82,$03,$00
EndDataSection

*a=AllocateMemory(12)
;           erg =     a      ^      b     mod      c 
; die beiden "2"er hier gebe die länge der Zahlen an "2" x 4BYTE(long)
NN_ModExp (*a,?Zahl1inhexLSB,?Zahl2inhexLSB,2,?Zahl3inhexLSB,2)

Debug speicherout_hex(*a,8,"")

; -> ergebnis 12 BB 29 98 C9 86 02 00

; LSB-MSB
;Ergebniss in hex "286C99829BB12"
;Ergebniss in dez "711150352841490"
auf Linux zur Verfügung stehen
jep
Wirst Du die in rsa.h angegebenen Funktionen auch einbauen
jep ... aber mache das immer nebenbei ... und somit dauert das ne Weile .. mom bin ich bei der RSA Keyerstellung ... aber die machen da riesenaufwand (2 Seiten Code um eine Zufallszahl zu erstellen ... nix mi9t random :mrgreen: )

Andi256
Alle Zeiten sind UTC+02:00
Seite 1 von 1

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de