RSA crypto

[Realizimo]

Code: Select all

;Rsa generator
EnableExplicit
Procedure rnd_r_prima(phie)
;finding the secret key "e"
Protected.q a,b,e, c
  Repeat
    a = phie  
    e = Random(phie,10)
    b = e
    ;If a>b :Swap a,b :EndIf
    Repeat
      c = a % b:a = b: b = c
    Until b = 0
   ; k+1
  Until a = 1
  ;If k>6:Debug k:EndIf
  ProcedureReturn e
EndProcedure 

Procedure Find_secret(phie,e)
;finding the secret key "d"
Protected.q d  
  For d = 1 To 100000
    If ((e * d) % phie) = 1 : ProcedureReturn d : EndIf
  Next d
  Debug "no secret":End
EndProcedure

Procedure rnd_Prime(min,max)
; Finding primnumber "p" and "q"  
Protected.q a, number , n, t,prime 
  For a=1 To 200
    prime =1
    number = Random(max,min)
    n = Sqr(number)
    For t = 2 To n
      If number % t = 0
        prime=0:Break
      EndIf
    Next t
    If prime =1:ProcedureReturn Number:EndIf
  Next a
  Debug "no prime": CallDebugger
EndProcedure

Procedure Bin_Mod_exp(m,e,n)
;finding "c" and "mm" the answer for (m^e mod n)
Protected.q k,c,cc,i  
  k=Len(Bin(e))
  c=m
  cc=m
  For i = k-1  To 1 Step -1
    c = (c * c) % n
    If (e & (1<<(k-i))) <>0 : cc*c: cc % n  : EndIf
  Next i
  ProcedureReturn cc
EndProcedure
       
Define.i i
Define.q p , q , phie , min
Define.q n , e , d  ; keys (n= public1 , e= random public2 , d= secret)
Define.q m , c , mm ; message

For i=1 To 10000
  
p = rnd_Prime(40,80)     ;min, max
Repeat
q = rnd_Prime(40,80)     ;min, max 
Until q <> p
; p=41
; q=43
n = p * q            
phie = (p-1)*(q-1)   

;If phie<0: CallDebugger:EndIf

e = rnd_r_prima(phie)    

d = Find_secret(phie , e) 

m = Random(1762) ; message   (41*43 = 1763, 1762=max)

c = Bin_Mod_exp(m,e,n); encrypted message

mm= Bin_Mod_exp(c,d,n); decrypted message

Debug Str(i)+ #TAB$ +Str(m)+#TAB$ +Str(c)+#TAB$ +Str(mm)+#TAB$ +Str(p)+#TAB$ +Str(q)+#TAB$ +Str(e)

If mm<>m :Debug "error  ":End:EndIf

Next i

Debug "ok"

[applePi]

Thanks Realizimo for the code, when i run it on winxp 32 with PB531 x86 or PB540b3 x86 it gives the error message For doesn't support quad variables. but it works with long. so i have switched to windows 7 /64 with PB x64 and your code runs okay. so i wonder if this is a bug in PB x86 .
http://purebasic.fr/english/viewtopic.p ... 5&p=365198

[Realizimo]

applePi
an upgrade "Procedure Find_secret(phie,e)" in line 22 now much faster

Code: Select all

;Rsa generator - use debugger for functionality
EnableExplicit

;finding the public key2 "e" -randomize relative prima
Procedure rnd_r_prima(phie)
Protected.q a,b,e, c
  Repeat
    a = phie  
    e = Random(phie,10)
    b = e
    ;If a>b :Swap a,b :EndIf
    Repeat
      c = a % b:a = b: b = c
    Until b = 0
   ; k+1
  Until a = 1
  ;If k>6:Debug k:EndIf
  ProcedureReturn e
EndProcedure 

;finding the secret key "d"
Procedure Find_secret(phie,e)
  Protected.q x,y,d,v,ee,f,q,r,c,dd
x = 0
y = 1
d = 1
v = 0 
ee = phie
f = e    
    While e<>1   
        q = ee / e
        r = ee % e
        c = x - q * d
        dd = y - q * v
        x = d
        y = v
        d = c
        v = dd
        ee = e
        e = r
    Wend
    d = (d + phie) % phie
ProcedureReturn d
EndProcedure

; Finding primnumber "p" and "q" 
Procedure rnd_Prime(min,max) 
Protected.q a, number , n, t,prime 
  For a=1 To 200
    prime =1
    number = Random(max,min)
    n = Sqr(number)
    For t = 2 To n
      If number % t = 0
        prime=0:Break
      EndIf
    Next t
    If prime =1:ProcedureReturn Number:EndIf
  Next a
  Debug "no prime": CallDebugger
EndProcedure

;finding "c" and "mm" the answer for (m^e mod n) -fast modular exponentiation binary method
Procedure Bin_Mod_exp(m,e,n)
Protected.q k,c,cc,i  
  k=Len(Bin(e))
  c=m
  cc=m
  For i = k-1  To 1 Step -1
    c = (c * c) % n
    If (e & (1<<(k-i))) <>0 : cc*c: cc % n  : EndIf
  Next i
  ProcedureReturn cc
EndProcedure
       
Define.i i
Define.q p , q , phie
Define.q n , e , d  ; keys (n= public1 , e= random public2 , d= secret)
Define.q m , c , mm ; message

For i=1 To 10000
  
p = rnd_Prime(400,600)     ;min, max - get prime
Repeat
q = rnd_Prime(400,600)     ;min, max - get prime 
Until q <> p
; p=41
; q=43
n = p * q            ;public key_1 

phie = (p-1)*(q-1)   

e = rnd_r_prima(phie)    ;public key_2 - get relative prime

d = Find_secret(phie , e) ;get secret key

m = Random(17620) ; message   (41*43 = 1763, 1762=max) see line 71,72  - 40~41~43

c = Bin_Mod_exp(m,e,n); encrypted message - the keys "e",and "n" are needed

mm= Bin_Mod_exp(c,d,n); decrypted message - the keys "d",and "n" are needed

Debug Str(i)+ #TAB$ +Str(m)+#TAB$ +Str(c)+#TAB$ +Str(mm)+#TAB$ +Str(n)+#TAB$ +Str(e)+#TAB$ +Str(d)

If mm<>m :Debug "error":End:EndIf

Next i

Debug "ok"