In this work, we present an implementation of a distributed algorithm for threshold RSA key generation. The implemented algorithm allows to generate threshold RSA keys without a trusted dealer. Moreover, the algorithm is designed in such a way that none of the participants is capable of deducing the private key with their known information. We provide a brief explanation of the algorithm in question and explain the corresponding implementation details.
El sistema criptogra co propuesto por Rivest, Shamir y Adleman [RSA78], mas conocido como RSA, es uno de los sistemas criptogra cos mas usados hoy en d a, tanto para cifrado como para rmado.
Sin embargo, hay veces en las que RSA simple no es su ciente, y se debe usar RSA con umbral. En los sistemas criptogra cos con umbral, la operacion privada (descifrar, por ejemplo), esta distribuida entre n participantes llamados nodos. Para realizar una operacion privada exitosa se requiere de la participacion de t de los n nodos. Esto ultimo permite que algunos de los nodos fallen. Por ejemplo, si se tiene un sistema de criptograf a umbral con tres nodos y umbral dos, se debe contar con dos de los tres nodos para realizar una operacion privada. Uno de los nodos puede dejar de funcionar y el sistema sigue siendo operativo.
Un problema complejo en un sistema RSA con umbral es la generacion de llaves. Es muy dif cil generar las llaves de manera tal que ningun participante tenga su ciente informacion para vulnerar el sistema, como Copyright c by the paper's authors. Copying permitted for private and academic purposes. la factorizacion del modulo RSA o los valores de las llaves privadas.
En el art culo [BF01], Boneh y Franklin propusieron un algoritmo que logra generar llaves RSA para criptograf a umbral de manera distribuida y segura. En este trabajo, introducimos una implementacion del algoritmo propuesto por Boneh y Franklin. 2 2.1
Hay algunos parametros que se deben entregar al algoritmo para que se pueda ejecutar: La cantidad de nodos que participaran: n, con n 3, el parametro umbral: t, con t > n2 , el taman~o en bits del modulo RSA: b y el exponente publico: e. 2.2
Al terminar la ejecucion del algoritmo, se tiene lo siguiente:
Una llave publica RSA compuesta por el exponente publico de nido anteriormente (e) y el modulo RSA N . N debe ser el producto de dos numeros primos y tener un taman~o de a lo mas b bits y a lo menos b 4 bits.
Una llave privada RSA d distribuida entre los n nodos participantes. La llave esta distribuida de tal manera que se puede realizar criptograf a umbral (basta que un subconjunto cualquiera de t nodos realice la operacion privada parcial para poder realizar una operacion privada exitosa). As , el nodo i esimo guarda la llave privada parcial di. 2.3
La siguiente es una descripcion de muy alto nivel de los pasos que sigue el algoritmo. La descripcion detallada del algoritmo esta en el art culo de Boneh y Franklin [BF01]. 1. El nodo i-esimo elige pi y qi. Al hacer esto, se debe tener en cuenta el taman~o deseado del modulo RSA N 2. Los nodos usan sus pi y qi para calcular un N candidato de acuerdo a la siguiente formula: N = p q = n X pi i=1 n X qi i=1 Este calculo se realiza sin exponer los pi y qi gracias a una version simpli cada de la tecnica BGW [BOGW88]. 3. Los nodos le realizan un test de biprimalidad a N . Si N es biprimo (producto de dos primos), se avanza al paso siguiente; si no, el algoritmo vuelve a comenzar desde el paso 1. Cabe destacar que no es necesario calcular p ni q expl citamente para determinar si N es producto de dos primos. El test de biprimalidad esta especi cado y probado en el art culo [BF01]. 4. A partir de N y e se calcula un conjunto de llaves preliminar fd0ig. Estas llaves cumplen que: d = n X d0
i i=1 El valor d ser a la llave privada en un sistema RSA simple con el mismo modulo N y el mismo exponente publico e. Con este conjunto preliminar no se puede hacer criptograf a umbral. 5. Usando el conjunto fd0ig, se calcula el conjunto nal de llaves fdig. A diferencia del conjunto preliminar, este conjunto nal s permite realizar criptograf a umbral. La tecnica que se ocupa para lograr el comportamiento umbral viene del trabajo de Rabin expuesto en el art culo [Rab98]. La gura 1 ilustra el orden en el que ocurren los pasos del algoritmo. Luego de especi car el algoritmo implementado, se procedio a implementar la solucion. En esta seccion se describe como se llevo a cabo la implementacion y algunos detalles particularles del software. Cada uno de los pasos del algoritmo explicados en la seccion 2.3 esta implementado en un modulo. A su vez, cada modulo contiene funciones que ejecutan las tareas necesarias para completar cada paso. Muchas de esas funciones son distribuidas e involucran que los nodos intercambien mensajes entre ellos para poder obtener el resultado de la funcion. Ademas, cada una de las tareas de la funcion se ejecuta en un proceso distinto.
As , si una funcion involucra calcular un valor, mandarle ese valor al resto de los nodos, recibir los valores respectivos del resto de los nodos y luego calcular un resultado nal, todas esas tareas se ejecutan en procesos distintos. Cuando las tareas se deben ejecutar serialmente, se lanza un proceso para la primera tarea y ese proceso se encarga de lanzar un proceso para la segunda tarea antes de terminar su ejecucion.
Cuando una de las funciones distribuidas se ejecuta, se debe ejectuar en todos los nodos del sistema a la vez. Los nodos trabajan cooperativamente para lograr resultados conjuntos utilizando estas funciones. 3.2
El modulo del algoritmo completo se encarga de componer las funciones principales de los modulos de los pasos (explicados anteriormente en la seccion 3.1) para obtener el ujo representado en la gura 1.
Para lograr lo anterior, tiene dos funciones: una funcion auxiliar que se encarga de generar un N candidato y una funcion principal recursiva que implementa el loop de la gura 1 y el comportamiento que sigue al loop. 3.3
El modulo de comunicacion es el que esta encargado de administrar toda la comunicacion que ocurre entre los nodos y un cliente que es el que solicita la generacion de llaves. Se eligio ocupar un modelo de comunicacion central en el que toda la comunicacion entre nodos es v a el cliente.
Dado lo anterior, este modulo tiene funciones para que los nodos puedan enviar y recibir mensajes y para que el cliente pueda distribuir correctamente los mensajes entre los nodos.
La gura 2 explica como uje la comunicacion entre procesos y nodos. 1. El proceso a del nodo 1 le quiere enviar un mensaje al proceso b del nodo 2. Ocupa la funcion send to node, especi cando el nodo al que le quiere enviar el mensaje e incluyendo el nombre del proceso destinatario dentro del mensaje. 2. La funcion le env a un mensaje al proceso que esta corriendo coord loop en el cliente. 3. El cliente le redirige el mensaje al proceso que esta corriendo la funcion node loop en el nodo destinatario. 4. El proceso de node loop le env a el mensaje al proceso destinatario, que esta indicado dentro del mensaje.
As , el cliente se encarga de determinar a que nodo entregarle los mensajes y dentro de cada nodo, el proceso que ejecuta la funcion node loop se encarga de determinar a que proceso del nodo entregarle los mensajes. 4
Primero, se realizaron varias pruebas del algoritmo completo para comprobar que estuviera correctamente implementado. Se veri co que todos los nodos llegaran al mismo valor de N , que con todas las combinaciones posibles de t llaves privadas se obtuviera el mismo valor de d y que el valor de d obtenido fuera equivalente al de un sistema RSA normal con modulo N y exponente publio e. Ademas, cuando el taman~o lo permit a, se comprobo que el modulo N obtenido fuera producto de dos primos. Todas las veri caciones anteriores fueron positivas, por lo que se concluyo que la implementacion del algoritmo esta correcta.
Ademas en cada experimento se midio la cantidad de intentos de generacion de modulo N que se debieron realizar. Luego, se calculo el promedio de intentos agrupados por taman~o de modulo y se comprobo con un valor esperado. Dicho valor esperado se obtuvo del teorema de los numeros primos [CP05], que indica que se deben realizar en promedio ( 2b ln 2)2 intentos para obtener un modulo biprimo (donde b es el taman~o deseado del modulo). El gra co de la Figura 3 muestra el resultado obtenido, donde se puede observar que el promedio de intentos obtenido fue mucho menor al esperado.
Implementar las optimizaciones del algoritmo propuestas en el art culo [BF01].
Agregar una capa de seguridad que cifre el tra co de datos entre los nodos. Para esto, lo ideal ser a usar cifrado simetrico (donde todos los nodos comparten una llave).
Probar un esquema distinto de comunicacion. [BF01]
Dan Boneh and Matthew Franklin. E cient generation of shared rsa keys. Journal of the ACM (JACM), 48(4):702{722,
July 2001. [BOGW88] M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault tolerant distributed computation. In Proc. STOC, pages 1{10, 1988. [CP05] [Rab98] [RSA78]
R. Crandall and C. Pomerance. Prime Numbers: A Computational Perspective, 2nd ed. Springer-Verlag, 2005.
T. Rabin. A simpli ed approach to threshold and proactive rsa. In Advances in Cryptology | CRYPTO, pages 89{104, 1998.
R. L. Rivest, A. Shamir, and L. Adleman.
A method for obtaining digital signatures and public-key cryptosystems. Commun.
ACM, 21(2):120{126, February 1978.