# L5 Laboratorio saioa: RSA gakoak
#  (Aritmetika Modularra: alderantzizko modularra)
#  (Zenbaki-teoria: Zenbaki osoen faktorizazioa)

# "numbers" paketea instalatzeko:
install.packages("numbers")
# "numbers" paketea kargatzeko:
library("numbers")

# laguntza eskatzeko:
library(help="numbers")

# RSA gakoen kalkulurako funtzio hauek bereziki interesatzen
# zaizkigu

# Bi zenbaki lehen aukeratzeko baliagarriak:
Primes(100000,100020)
nextPrime(100000)
previousPrime(100019)

# Alderantzizko modularren kalkulua. 
# numbers paketeko bi funtzio erabiliz kalkula dezakegu:
# modinv(n,m) funtzioa (Modular Inverse)
# Computes the modular inverse of n modulo m.
# 3aren alderantzizkoa modulu 64 kalkulatzeko:
modinv(3,64)
#  3^-1 mod 64=43
# Begira ezazu funtzioa nola inplementatuta dagoen: 
modinv

# Alderantzizko modularra Euklidesen algoritmoa erabiliz kalkulatzen da.
# Zatitzaile komunetako handienaren 5. propietatea 
# (Bezout-en identitatea): zkh(a,b)=xa+yb 
# extGCD(a,b) funtzioa (Extended Euclidean Algorithm)
# Computes the greatest common divisor and solves Bezout's identity.
# 3aren alderantzizkoa modulu 64 kalkula dezagun: 3^-1 mod 64=?
extGCD(3,64)
1==-21*3+1*64
# 3-aren alderantzizkoa konbinazio lineal horretan 3ak aldamenean duen 
# koefizientea da. zkh(a,b)=xa+yb --> 1==-21*3+1*64 --> x=-21
# 64 moduluko kongruentzian, -21+64=43. Hortaz, 3^-1 mod 64=43
-21+64

# Zenbakien faktorizazioa (deskonposaketa zenbaki lehenetan):
primeFactors(1448)
primeFactors(1001)


# R softwareak zenbaki handiak idazkera zientifikoan erakusten
# ditu. Hala egiterik nahi ez badugu, idazkera zientifikoa desaktibatu 
# dezakegu
a=nextPrime(2634758697353)
a
# 2.634759e+12 --> Ze zenbaki da hori?
# Zenbaki lehen hori zein den zehazki ikusi nahi dugu...

format(a, scientific=FALSE)
# "2634758697451"

###############################################################
# 1. Ariketa. RSA gakoen kalkulurako funtzioa
# Bi zenbaki lehen emanik, p eta q, RSA_gakoak(p,q) funtzioak
# n, r eta s kalkulatuko ditu. r txikia kalkulatuko da.

# L4 laboratorio saioko funtzioa erabiliko dugu:
lehen_erlatibo_txiki <- function(m)
{
  zbki<-2;
  while(GCD(m,zbki)!=1) ## L4 laboko zkh funtzioa erabil daiteke
  {
    zbki<-zbki+1;
  };
  return(zbki);
}

RSA_gakoak <- function(p,q)
{
  if(p!=q){
  n<-p*q
  m<-(p-1)*(q-1)
  r<-lehen_erlatibo_txiki(m)
  s<-modinv(r,m)
  gakoak<-cat("Gako publikoa: n: ",n,"r: ",r,"Gako pribatua. s: ",s,"\n")
  return(gakoak)
  }
  else{
    print("p eta q ezin dira berdinak izan")
    return()
    }

  
}

# Probak:
# Aritmetika modularra gaiko ariketen orriko 9. ariketakoak dira
# RSA_gakoak(17,23) eskuzko kalkulua RSA algoritmoari buruzko 
# orri teorikoetan agertzen da
RSA_gakoak(5,17)
RSA_gakoak(17,23)
RSA_gakoak(97,101)
RSA_gakoak(307,397)
#Nire gako pribatuak
RSA_gakoak(643,443)
Primes(400,700)
# Froga ezazu R erabiliz gako horiek ez direla seguruak:







# wikipediako zenbaki lehenen zerrendako bi zenbaki handirekin
# egin proba. Ea horiek seguruak diren...










###########################################################
## 2. ariketa. RSA_gako_handiak funtzioa
# RSA_gakoak funtzioari hobekuntzak:
# Zenbaki handiekin lan egitera bideratuak.
# 1.- Parametro moduan bi zenbaki oso eta positibo jasoko ditu. 
# 2.- r gako publikoa handia izatea nahi dugu

## L4 laboan inplementatutako lehen_erlatibo funtzioa erabil
# dezakezu.
lehen_erlatibo <- function(m,atalasea)
{
  zbki<-atalasea;
  #  while(zkh(m,zbki)!=1) # isNatural funtzioak zenbaki handiekin arazoak
  while(GCD(m,zbki)!=1)
  {
    zbki<-zbki+1;
  };
  return(zbki);
}


RSA_gako_handiak <- function(a,b)
{
  p<-nextPrime(a)
  q<-nextPrime(b)
  if(p!=q){
    n<-p*q
    m<-(p-1)*(q-1)
    r<-lehen_erlatibo(m,a+b)
    s<-modinv(r,m)
    gakoak<-cat("Gako publikoa: n: ",format(n, scientific=FALSE),"r: ",format(r, scientific=FALSE),"Gako pribatua. s: ",format(s, scientific=FALSE),"\n")
    return(gakoak)
  }
  else{
    print("p eta q ezin dira berdinak izan")
  }
  

}

# Probak:
# Idazkera zientifikoa ekidin gabe:
RSA_gako_handiak(2634758697353,293756536383)

# Idazkera zientifikoa ekidinda:
RSA_gako_handiak(2634758697353,293756536383)


# Non dago muga? Begira ezazu primeFactors 
# funtzioaren inplementazioa:
primeFactors(773977589210346518740992)


# Probak zenbaki handiekin:

RSA_gako_handiak(30000000,300000000)
# p= 30000001 q= 300000007 n= 9000000510000007 r= 30000001 s= 2249999970000001 

RSA_gako_handiak(300000000,3000000000)
# p= 300000007 q= 3000000019 n= 900000026700000128 r= 300000001 s= NA 

RSA_gako_handiak(2634758697353,293756536383)
# p= 2634758697451 q= 293756536399 n= 773977589210346518740992 
# r= 2634758697353 s= 391747678355017485516800 

## n hori ezin da faktorizatu:
primeFactors(773977589210346518740992)
# NA
#Warning message:
#  In primeFactors(7.73977589210347e+23) :
#  Argument 'n' too big: use 'gmp::factorize()' for this.


# Non dago muga? 
# Begiratu primeFactors funtzioaren inplementazioa




# Aukeratzen ditugun bi zenbaki lehenek zer bete behar dute sistema segurua izateko?