Criptografia RSA completa totalmente escrita em Rubi

rsa.rb

#################################################################
# O ALGORITMO ASSIMÉTRICO RSA COMPLETO
# PROGRAMADOR: YUGI	
# DATA: 27/12/2011
#################################################################

# ============================================================================================
# OBSERVAÇÕES:
# AQUI NÓS TEMOS A CRIPTOGRAFIA RSA TOTALMENTE ESCRITA EM RUBI
# UMA CHAVE DE 1024 BITS PODE SER GERADA EM MENOS DE 2 MINUTOS
# UMA CHAVE DE 2048 BITS PODE SER GERADA EM 10 MINUTOS
# UMA CHAVE DE 4096 BITS PODE SER GERADA EM 1 HORA (PODENDO LEVAR MAIS TEMPO)
# UMA CHAVE DE 8192 BITS PODE LEVAR MUITAS HORAS PARA SER GERADA
# COMO RUBI É UMA LINGUAGEM INTERPRETADA ELA É MUITO MAIS LENTA DO QUE C, POR EXEMPLO.
# --------------------------------------------------------------------------------------------
# OBS2: TESTES FEITOS EM PROCESSADOR INTEL 2,4 GHZ
# ============================================================================================

require 'ftools'	

def hora()
	agora = Time.new
	puts agora.strftime("%d/%m/%Y - %H:%M:%S")
	return agora.strftime("%H:%M:%S")
end
# ---------------------------------------------------------------------
# CALCULA O MÁXIMO DIVISOR COMUM ENTRE DOIS NÚMEROS

def mdc(n1,n2)

	if n1 > n2
		max = n1
		min = n2
	else
		max = n2
		min = n1
	end

	while TRUE
		mdc = min
		tmp = max % min
		max = min
		min = tmp
		if min == 0
			break
		end	
		if max == 1
			mdc = 1
			break
		end
	end	

	return mdc
end

# ---------------------------------------------------------------------
# CALCULA O MÍNIMO MULTIPLO COMUM DE DOIS NUMEROS

def mmc(n1,n2)
	
	tmp = mdc(n1,n2)
		
	mmc = n1 * (n2 / tmp)	

	return mmc
end

# ---------------------------------------------------------------------
# FUNÇÃO PARA EXPONENCIAÇÃO RÁPIDA:

def pot(n,exp,base)
	exp = exp -1
	p = n

	if exp == 0
		return 1
	end
	if exp == 1
		return n
	end

	if exp <= 1000
		for cont in (1..exp)
			n = (n * p) % base
		end
		return n
	else	
	# 	DINAMIZANDO A POTENCIAÇÃO...

			vetormapa = Array.new
			for xcont in (0..1000)
				vetormapa[xcont] = 1
			end

			tmp = p	
			xcel = 0
			xzero = 1000

				while TRUE
					for cont in (1..1000)	
						vetormapa[xcel] = (vetormapa[xcel] * tmp) % base
					end		
					tmp = vetormapa[xcel]
					xcel = xcel + 1

					xzero = xzero * 1000
					if exp < xzero
						break
					end	

					if xcel > 1000
						break
					end
				end

		result = 1
		exp = exp + 1

		# Gerencimento para operacoes com números gigantes:

		xcont = 1000

		xzero = 1
		for ct in (0..1000)
			xzero = xzero * 1000
		end

			while TRUE
				if exp >= xzero
					while TRUE
						if exp >= xzero
							result = (result * vetormapa[xcont]) % base
							exp = exp - xzero
						else
							break
						end
					end
				end
				xzero = xzero / 1000
				xcont = xcont -1
				if xcont < 0
					break
				end
			end	

		n = result
		for cont in (1..exp)
			n = (n * p) % base
		end
		
		return n
	end

end
# ----------------------------------------------------------------------

# ALGORITMO DE RABIN MILLER, VERIFICA SE UM NÚMERO PODE SER PRIMO

def rmiller(n,xint)
	# a entrada deve ser um número ímpar e maior do que 3	
	# calculando n-1 na forma 2^s * d, onde d é ímpar
	
	prime = FALSE
	k = 0
	m = n -1
	a = b = j = 0

	while (m % 2 == 0)
		m = m / 2
		k = k + 1
	end

	verif = 0

	while (!prime && j < xint)
		a = rand(n) % (n-1)		# testemunha

		if xint == 1
			a = a % 1_000_000_000
		end

		if a <= 1
			a = a + 2
		end

		b = pot(a,m,n)

		if b == 1
			prime = TRUE
		else
			for cont in (1..k)
				if (b == n-1)
					prime = TRUE
					break
				else
					b = (b * b) % n
				end
			end
		end
		
		j = j + 1
	end

if prime == TRUE 
	#puts "O Número " + n.to_s + " pode ser primo | Rounds.: " + j.to_s
else
	puts "O número " + n.to_s + " é composto | Rounds.: " + j.to_s
end	

	if prime == TRUE
		return n	# retorna o número caso ele for primo
	else
		return 0	# caso contrário retorna 0
	end

end

# ----------------------------------------------------------------------
# CALCULA O INVERSO MULTIPLICATIVO DE UM NÚMERO POR UMA BASE

def invmul(numero, base)

	if numero >= base
		puts "ERRO: A BASE DEVE SER MAIOR QUE O NÚMERO"
		exit
	end

	if mdc(base,numero) != 1
		puts "NÚMERO E BASE DEVEM SER PRIMOS ENTRE SI!"
		exit
	end

	cof = Array.new
	posic = 0
	basex = base
	num = numero

	while (num > 1)
		tmp = 1
		
		tmp = basex / num
		if tmp > 1
			tmp = tmp - 1
		end
	
		while TRUE
			if num * tmp >= basex
				cof[posic] = tmp - 1
				posic = posic + 1
				break
			end
			tmp = tmp + 1
		end
		tmp = basex
		basex = num
		num = tmp - (num * cof[posic-1])
	end

	vet = Array.new
	tam = cof.length
	tam = tam -1
	posic = tam
	for cont in (0..tam)
		vet[posic] = cof[cont]
		posic = posic -1
	end

	varJ = 0
	varB = 1
	tam = vet.length
	tam = tam -1

	for cont in (0..tam)
		varR = varJ + (varB * vet[cont])
		varJ = varB
		varB = varR
	end

	tam = cof.length

	if tam % 2 == 0
		inv = varR
	else
		inv = base - varR
	end

	return inv
end
# --------------------------------------------------------------------

# Função que retorna todos os números primos até 1.000.000
def mapaprimo()
	limite = 1_000_000
	xcont = 5
	num = 13

	mapaprimo = Array.new
	mapaprimo[0] = 2
	mapaprimo[1] = 3
	mapaprimo[2] = 5
	mapaprimo[3] = 7
	mapaprimo[4] = 11


	while TRUE
		primo = TRUE
		divide = 3
		cont = 0
		tam = mapaprimo.size
		tam = tam -1

		while TRUE
			if num % divide == 0
				primo = FALSE
				break
			end

			if cont <= tam
				divide = mapaprimo[cont]
			else
				break
			end
			if (divide * divide) > num
				break
			end
			cont = cont + 1
		end
		if primo
			mapaprimo[xcont] = num
			xcont = xcont + 1
		end

		num = num + 2
		if num > limite
			break
		end
	end

	return mapaprimo
end
# ----------------------------------------------------------------------------

# gera um número aleatório até um dado limite
def geranum(limite)
	num = rand(limite)

	num = num % limite
	tam = num.to_s.length
	tam = tam -1 
	
	for cont in (1..tam)
		muda = rand(10) % 10
		num = (num + muda) % limite
		xnum = num.to_s
		xtam = xnum.length
		xnum = xnum[1,xtam-1] + xnum[0,1]
		num = xnum.to_i % limite
	end

	if num <= 2
		num = num + 1
	end
	return num
end
# --------------------------------------------------------------------------------

# calcula o tempo de um processamento
def calctime(ini,fim)
	n1 = (ini[0,2].to_i * 3600) + (ini[3,2].to_i * 60) + ini[6,2].to_i
	n2 = (fim[0,2].to_i * 3600) + (fim[3,2].to_i * 60) + fim[6,2].to_i
	
	result = n2 - n1
	hora = minuto = segundo = 0

	while TRUE
		if result >= 3600
			result = result - 3600
			hora = hora + 1
		else
			break
		end	
	end

	while TRUE
		if result >= 60
			result = result - 60
			minuto = minuto + 1
		else
			break
		end	
	end

	while TRUE
		if result >= 1
			result = result - 1
			segundo	= segundo + 1
		else
			break
		end	
	end

	vh = hora.to_s
	if vh.length ==1
		vh = "0" + vh
	end

	vm = minuto.to_s
	if vm.length ==1
		vm = "0" + vm
	end

	vs = segundo.to_s
	if vs.length ==1
		vs = "0" + vs
	end

	return vh + ":" + vm + ":" + vs
	
end
# --------------------------------------------------------------------------
# Esta a funcao pricipal que chama todas as outras...
# Com ele podemos gerar uma chave RSA de 1024, 2048, 4096 e até mesmo 8192 bits...
# o segundo parametro permite testar mais vezes o suposto primo encontrado
def gerachave(tam_chave,xverifica)

	if xverifica < 1 
		xverifica == 1
	elsif xverifica > 20 
		xverifica == 20
	end

	if tam_chave != 1024 && tam_chave != 2048 && tam_chave != 4096 && tam_chave != 8192
		puts "Tamanho de chave inválido! Escolha um destes valores: 1024, 2048, 4096 ou 8192 bits."	
		exit
	end

	ini = hora()

	puts "GERANDO UMA CHAVE PÚBLICA PARA O ALGORITMO RSA"
	puts ""
	puts "Aguarde, Preparando para os cálculos..: Chave de " + tam_chave.to_s + " bits."

	vetprimo = mapaprimo()

	arq = File.new("Chave-RSA.txt","w+")

	chave = Array.new
	vg = 0
	posic = 0

	while TRUE
		while TRUE
	
			falha = 0

			# Gerenciando o tamanho da chave:
			if tam_chave == 1024
					tnum = "000" * 60	# primo  512 bits - gera chave de 1024
				elsif tam_chave == 2048
					tnum = "000" * 120	# primo 1024 bits - gera chave de 2048
				elsif tam_chave == 4096
					tnum = "000" * 240	# primo 2048 bits - gera chave de 4096
				elsif tam_chave == 8192
					tnum = "000" * 480	# primo 4096 bits - gera chave de 8192
				else
					puts "Tamanho de chave inválido! Escolha um destes valores: 1024, 2048, 4096 ou 8192 bits."
					exit
			end

			tnum = "1" + tnum
			limite = tnum.to_i


			while TRUE 
				teste = geranum(limite)

				if tam_chave == 1024
					if teste.to_s.length >= 160	# Garante número Mínimo de dígitos
						break
					end
				elsif tam_chave == 2048
					if teste.to_s.length >= 320
						break
					end
				elsif tam_chave == 4096
					if teste.to_s.length >= 640
						break
					end
				elsif tam_chave == 8192
					if teste.to_s.length >= 1280
						break
					end
				end
			end

	
				if teste % 2 == 0
					teste = teste + 1
				end

				# verifica se o número é divisível por qualquer primo até 1.000.000
				vetprimo.each do |valor|
					if teste % valor == 0
						falha = 1
						break
					end
				end


			if falha == 0	
				#hora()
				puts teste
				if rmiller(teste,1) != 0
					puts hora() + " | É um forte candidato a ser primo!!!"
					break
				end	
				hora()
			end

			posic= posic + 1
			if vg != 0
				puts "Um número primo já foi encontrado e até agora " + posic.to_s + " foram analisados!"
			end

		end

			k = 0
			for cont in (1..xverifica)
				if rmiller(teste,100) != 0
					k = k + 1
				else
					break	
				end
			end

			if k == xverifica
				puts teste.to_s + " é muito provavelmente um número primo!!!"	
				tmp = teste.to_s + "\n"
				arq.write tmp
				chave[vg] = teste
				vg = vg + 1
			end

			if vg >= 2
				break	
			end
	end

	# Gerando a chave Pública RSA:


		chN = chave[0] * chave[1]	
		chR = (chave[0]-1) * (chave[1]-1)
		chD = chE = 0

		while TRUE
			chE = geranum(chR)
			if mdc(chE,chR) == 1 && chE < chR
				break
			end
		end
	
		chD = invmul(chE,chR)	# Gerando a chave privada...
	
		if (chD * chE) % chR != 1
			puts "Erro no calculo do inverso multiplicativo"
			exit
		end

		arq.write "\n"
		arq.write "Chave Pública.: \n"
		arq.write chE.to_s + "\n"
		arq.write chN.to_s + "\n"
		arq.write "\n"
		arq.write "Chave Privada.: \n"
		arq.write chD.to_s + "\n"
		arq.write chN.to_s + "\n"

	arq.close

	puts "Tempo de Processamento: " + calctime(ini,hora())
	puts "fim"
	puts ""
	puts "Testando a sua chave Pública..."

	# Validacao da chave gerada:

		limite = chN / 1000	# Limite do tamanho do texto para testar a chave...

		for ct in (1..2)
			texto = geranum(limite)
			# codificando:
			cripto = pot(texto,chE,chN)
			# decodificando:
			decod = pot(cripto,chD,chN)

			if texto == decod
				puts "Teste " + ct.to_s + ": Confere - OK" 
			else
				puts "ERRO na decifragem - Gere outra Chave!!!"
				break
			end
		end

	puts ""
	puts ""
	puts "SUA CHAVE RSA DE " + tam_chave.to_s + " bits foi gerada com sucesso e está registrada no arquivo Chave-RSA.txt!!!"
end
# =====================================================================================================================

# EXEMPLO DE CHAMADA DA FUNÇÃO:

#gerachave(1024,5)
gerachave(2048,5)
#gerachave(4096,5)
#gerachave(8192,5)