RSA POC

draft_notes.rb

def encript(e_, n_, m_ ){
  p 'm ^ e'
  p m_ ** e_
  p 'c_ (encripted message)'
  p c_ =  (m_ ** e_) % n_
}

p_ = 11
q_ = 13
n_ = p_ * q_
p 'n'
p n
e_ = 3
m_ = 26

encript(e_ , n_, m_)
# two chained exponentiatinons are equal to one exponentiation of the multiplication of the exponents
# (m_ ** e_) ** d_ = (m_ ** (e_ * d_))
# left side:
# (2  ** 3 ) ** 3
# (2 * 2 * 2 ) * (2 * 2 * 2) * (2 * 2 * 2)
# 2 ** 9
# right side
# (2  ** (3 * 3))
# 2 ** 9
# same result


p c
p 'knowing that p and q are primes'
p " number_of_numbers_that_dont_share_a_factor_with_p #{p_}"
p totient_of_p = p_ -1
p " number_of_numbers_that_dont_share_a_factor_with_q #{q_}"
p totient_of_q = q_ -1
p "since totient (p * q) = totient (p) * totient(q)"
p "totient of #{n} (n) =  (number_of_numbers_that_dont_share_a_factor_with_n)"
p 'totient_of_p * totient_of_q'
p totient = totient_of_p * totient_of_q


# ((m_ ** e_ ) % n_ )** d_)) % n_ == m_
# (encripted        )** d_)) % n_ == decripted
# d_ ????
# wich d will decript our encripted ?
# side note
# applying the module both times or just at the end gives equal results
# (m_ ** e_ ) % n_ ) ** d_ % n_ == decripted is equal to
# ((m_ ** e_ ))** d_)) % n_ == m_
# ( (A % C)**B ) % C == A**B % C (modular exponentiation property)

# (m_ ** e_ )** d_)) % n_ == m_      is equal to:
# (m_ ** (e_ * d_)) % n_ == m_

# Eulers theorem
# m ** (totient(n)) ==== 1 mod n
# given m and n dont share a common factor, ie: n is prime, ie n == 3
# m ** (totient(n)) ==== 1 mod n
# we are going to rearrange this equaliy to get what we need ! ........ :
# (m_ ** (e_ * d_)) % n_ == m_                 # d ????

# Eulers theorem
# m ** (totient(n)) ==== 1 mod n
# exponentiate both sides by k (any number)
# ( m ** (totient(n))  ) ** k  ==== (1 mod n ) ** k
# modular exponentiation property
# ( m ** (totient(n))  ) ** k  ==== (1 ** k ) mod n
# 1 ** any number will always be equal to 1
# ( m ** (totient(n))  ) ** k  ==== 1 mod n
# two chained exponentiatinons are equal to one exponentiation of the multiplication of the exponents
# m ** (totient(n) * k ) === 1 mod n
# multiply both sides by m
# (m ** (totient(n) * k )) * m === (1 mod n) * m
# multiplying an exponentiation by the number that is exponentiated is equal to just sum 1 to the exp
# m ** (totient(n) * k  + 1) === (1 mod n) * m
# right side: 1 * m === m
#  m  ** (totient(n) * k  + 1) ===  m mod n
#
#  m_ ** (    e_ * d_        ) ===  m_ %  n_
# then !
# totient(n) * k  + 1 === e_ * d_
# (totient(n) * k  + 1) / e_ === d_
# p * q = n
# the totient has a multiplication property ...... :
# totient (n) = totient (p) * totient (q)
# the totient is easy to calculate if a number is prime.  totient(p) = p - 1
# the totient is hard to calculate if a number is not prime. totient(m) = ???
# we know n = p (prime) * q (prime) because we constructed n like that on porpouse
d_ = (  ((p_ - 1) * (q_ -1) * k_) + 1   ) / e
d_ = (  (totient(n)         * k_) + 1   ) / e
# we dont know k_ yet
d_ * e = (totient(n)   * k_) + 1
d_ = totient(n) * k_ : e + 1 : e
d_ = (p_ - 1) * (q_ -1) : e * k_ + 1 : e
d_ = tot : e * k + 1 : e
   = 3016 : 3 *k + 1 : 3



k has to bu such that it decimal part of the first summed componen is equal to :
= 1 - 1 : e
= (e -1) / e

the decimal part of tot : e would be equal to :
if tot is a multiple of 3 there is no decimal part , so n is useless
tot / e =
4 / 3 => (4 mod 3)  / 3 => 1/3
5 / 3 => (5 mod 3) / 3 => 2/3
siempre te va a quedar una fracción compatible, es solo multiplicar hasta que se encuentre
hay tantos casos como el modulo, en este caso, 3: 0, 1, 2
tot mod e  = 0, 1 , 2
si tot mod e = 1  entonces d va a ser igual a e -1 # o en todos los casos?

      :  1      2      3      4     5
1 / 5 = 0.2 => 0.4 => 0.6 => 0.8 => 1
2 / 5 = 0.4 => 0.8 => 1.2 => 1.6 => 2
3 / 5 = 0.6 => 1.2 => 1.8 => 2.4 => 3
4 / 5 = 0.8
5 / 5 = 1

tot : e * k + 1 : e

3016 : 5 * k + 1 : 5

k === e -1 ???
13 * 11
def encript(m_, e_, p_, q_ ){
  n_ = p_ * q_
  tot = (p_ -1) * (q_ -1)
  s_ = (m_ ** e_ ) % n_
  d_ = nil
  possible_d = (1...e_).to_a
  possible_d.each |pos| do
    d_candidate = ((pos.to_f * tot) + 1) / e_
    if d_ == d.floor
      d_ = d_candidate
    end
  end
  d_ = ((k_.to_f * tot) + 1) / e_
  desen = (m_ ** d_ ) % n_
  {"d"=> d_ , "e"=> e_ , "s_" => s_, 'k'=>k_,'m_' => m_, 'desen'=> desen }
}

RSA_POC.rb

require 'prime'

def prompt_number(*args)
    print(*args)
    result = gets.strip
    result.to_i
end

def generateModuloAndPublicExponent(prime_a, prime_b )
  # el móduo es:
  modulo = prime_a * prime_b
  # el totient del módulo es:
  totient = (prime_a -1) * (prime_b -1)

  public_exponent = nil
  # e_has to be coprime to prime_a and prime_b
  possible_e = (3...(30)).to_a
  possible_e.each do |pos_e|
    # candidato para el public exponent : + pos_e.to_s
    count = 0
    pos_e.prime_division.each do | div|
      if((prime_a -1) % div[0] == 0)
        break
      end
      if((prime_b -1) % div[0] == 0)
        break
      end
      count += 1
    end
    if count == pos_e.prime_division.length
      # encontrado un exponente público adecuado
      public_exponent = pos_e
      break
    end
  end

  k_ = nil
  possible_k = (1...(public_exponent )).to_a
  # hay que buscar un k tal que el exponente privado sea un entero
  possible_k.each do |pos_k|
    # 'candidato :' + pos_k.to_s
    # p 'el exponente privado sería : '
    private_exponent_would_be = ((pos_k.to_f * totient) + 1) / public_exponent
    if private_exponent_would_be == private_exponent_would_be.floor.to_f
      # p 'k encontrado'
      k_ = pos_k
      break
    end
  end
  # p 'el exponente privado es '
  private_exponent = ((k_.to_f * totient) + 1) / public_exponent

  {"private_exponent"=> private_exponent ,"public_module"=> modulo, "public_exponent"=> public_exponent , 'k'=>k_}
end

def modExponentiation(mod, exponent, number)
  partial = number
  (exponent - 1).times do |time|
    partial = (partial * number) % mod
    # p time
  end
  partial
end

def encryptAMessage(public_module, public_exponent, message)
  if (public_module - 1) < message
    raise ArgumentError.new("el mensaje es muy grande, tiene que ser más chico que primoA * primoB ( #{modulo}). Usar primos más grandes o usar un mensaje mas corto ")
  end

  modExponentiation(public_module, public_exponent, message)
  # equivalent to below but more efficient
  # (message ** public_exponent ) % public_module
end

def decryptAMessage(prime_a, prime_b, encrypted_message)
  p rsa = generateModuloAndPublicExponent(prime_a, prime_b)
  modExponentiation(rsa['public_module'], rsa['private_exponent'].to_i, encrypted_message)
  # equivalent to below but more efficient
  # (encrypted_message ** rsa['private_exponent'].to_i ) % rsa['public_module']
end

action = prompt_number "1) generar claves a partir de primos \n2) encriptar \n3) desencriptar\n"
if action == 1
  prime_example_a = prompt_number "ingresar un nro primo de no mas de 4 digitos: \n"
  prime_example_b = prompt_number "ingresar otro nro primo de no mas de 4 digitos: \n"
  rsa_data =  generateModuloAndPublicExponent(prime_example_a, prime_example_b)
  p rsa_data
elsif action == 2
  public_exponent = prompt_number "ingresar el exponente pùblico\n"
  public_module = prompt_number "ingresar el módulo pùblico\n"
  message = prompt_number "ingresar un nro a encriptar (más pequeño que #{public_module})\n"
  encrypted =  encryptAMessage(public_module, public_exponent, message)
  p 'encriptado'
  p encrypted
elsif action == 3
  private_exponent = prompt_number "ingresar el exponente privado\n"
  public_module = prompt_number "ingresar el módulo público\n"
  message = prompt_number "ingresar un nro a desencriptar\n"
  decripted = modExponentiation(public_module, private_exponent, message)
  p 'desencriptado'
  p decripted
else
  p 'eres una gran deshonra para tu familia'
end

RSA_verbose.rb

require 'prime'

def encript(message, prime_a, prime_b )
  p 'el móduo es:'
  p modulo = prime_a * prime_b
  if (modulo - 1) < message
    raise ArgumentError.new("el mensaje es muy grande, tiene que ser más chico que primoA * primoB ( #{modulo}). Usar primos más grandes o usar un mensaje mas corto ")
  end
  p 'el totient del módulo es:'
  p totient = (prime_a -1) * (prime_b -1)
  public_exponent = nil
  # e_has to be coprime to prime_a and prime_b
  possible_e = (3...(30)).to_a
  possible_e.each do |pos_e|
    p 'candidato para el public exponent :' + pos_e.to_s
    count = 0
    pos_e.prime_division.each do | div|
      if((prime_a -1) % div[0] == 0)
        break
      end
      if((prime_b -1) % div[0] == 0)
        break
      end
      count += 1
    end
    if count == pos_e.prime_division.length
      p 'encontrado un exponente público adecuado'
      p public_exponent = pos_e
      break
    end
  end

  p 'mensaje encriptado'
  p encripted_message = (message ** public_exponent ) % modulo

  k_ = nil
  possible_k = (1...(public_exponent )).to_a
  p 'hay que buscar un k tal que el exponente privado sea un entero'
  possible_k.each do |pos_k|
    p 'candidato :' + pos_k.to_s
    p 'el exponente privado sería : '
    p private_exponent_would_be = ((pos_k.to_f * totient) + 1) / public_exponent
    if private_exponent_would_be == private_exponent_would_be.floor.to_f
      p 'k encontrado'
      k_ = pos_k
      break
    end
  end
  p 'k'
  p k_
  p 'el exponente privado es '
  p private_exponent_ = ((k_.to_f * totient) + 1) / public_exponent
  desen = (encripted_message ** private_exponent_.to_i ) % modulo
  {"exponente privado"=> private_exponent_ ,"modulo_publico"=> modulo, "exponente_público"=> public_exponent , "encripted_message" => encripted_message, 'k'=>k_,'message' => message, 'desen'=> desen }
end

p encript(111, 197, 199)