Implementation of a Distributed Algorithm for Threshold RSA Key Generation Caterina Muñoz Vildósola caterina@niclabs.cl NIC Chile Research Labs University of Chile la factorización del módulo RSA o los valores de las Abstract llaves privadas. En el artı́culo [BF01], Boneh y Franklin propusieron In this work, we present an implementation un algoritmo que logra generar llaves RSA para crip- of a distributed algorithm for threshold RSA tografı́a umbral de manera distribuida y segura. En key generation. The implemented algorithm este trabajo, introducimos una implementación del al- allows to generate threshold RSA keys with- goritmo propuesto por Boneh y Franklin. out a trusted dealer. Moreover, the algorithm is designed in such a way that none of the par- 2 El Algoritmo ticipants is capable of deducing the private key 2.1 Parámetros de Entrada with their known information. Hay algunos parámetros que se deben entregar al al- We provide a brief explanation of the algo- goritmo para que se pueda ejecutar: La cantidad de rithm in question and explain the correspond- nodos que participarán: n, con n ≥ 3, el parámetro ing implementation details. umbral: t, con t > n2 , el tamaño en bits del módulo RSA: b y el exponente público: e. 1 Introducción 2.2 Resultados del Algoritmo El sistema criptográfico propuesto por Rivest, Shamir y Adleman [RSA78], más conocido como RSA, es uno Al terminar la ejecución del algoritmo, se tiene lo sigu- de los sistemas criptográficos más usados hoy en dı́a, iente: tanto para cifrado como para firmado. Sin embargo, hay veces en las que RSA simple no • Una llave pública RSA compuesta por el ex- es suficiente, y se debe usar RSA con umbral. En los ponente público definido anteriormente (e) y el sistemas criptográficos con umbral, la operación pri- módulo RSA N . N debe ser el producto de dos vada (descifrar, por ejemplo), está distribuida entre n números primos y tener un tamaño de a lo más b participantes llamados nodos. Para realizar una op- bits y a lo menos b − 4 bits. eración privada exitosa se requiere de la participación • Una llave privada RSA d distribuida entre los n de t de los n nodos. Esto último permite que algunos nodos participantes. La llave está distribuida de de los nodos fallen. Por ejemplo, si se tiene un sistema tal manera que se puede realizar criptografı́a um- de criptografı́a umbral con tres nodos y umbral dos, bral (basta que un subconjunto cualquiera de t no- se debe contar con dos de los tres nodos para realizar dos realice la operación privada parcial para poder una operación privada. Uno de los nodos puede dejar realizar una operación privada exitosa). Ası́, el de funcionar y el sistema sigue siendo operativo. nodo i−ésimo guarda la llave privada parcial di . Un problema complejo en un sistema RSA con um- bral es la generación de llaves. Es muy difı́cil generar 2.3 Descripción General del Algoritmo las llaves de manera tal que ningún participante tenga suficiente información para vulnerar el sistema, como La siguiente es una descripción de muy alto nivel de los pasos que sigue el algoritmo. La descripción detallada Copyright c by the paper’s authors. Copying permitted for del algoritmo está en el artı́culo de Boneh y Franklin private and academic purposes. [BF01]. 1. El nodo i-ésimo elige pi y qi . Al hacer esto, se debe 3.1 Módulos de Pasos tener en cuenta el tamaño deseado del módulo RSA N Cada uno de los pasos del algoritmo explicados en la sección 2.3 está implementado en un módulo. A su 2. Los nodos usan sus pi y qi para calcular un N vez, cada módulo contiene funciones que ejecutan las candidato de acuerdo a la siguiente fórmula: tareas necesarias para completar cada paso. Muchas n X n  X  de esas funciones son distribuidas e involucran que los N =p·q = pi · qi nodos intercambien mensajes entre ellos para poder i=1 i=1 obtener el resultado de la función. Además, cada una de las tareas de la función se ejecuta en un proceso Este cálculo se realiza sin exponer los pi y qi gra- distinto. cias a una versión simplificada de la técnica BGW Ası́, si una función involucra calcular un valor, man- [BOGW88]. darle ese valor al resto de los nodos, recibir los valores respectivos del resto de los nodos y luego calcular un 3. Los nodos le realizan un test de biprimalidad a resultado final, todas esas tareas se ejecutan en pro- N . Si N es biprimo (producto de dos primos), se cesos distintos. Cuando las tareas se deben ejecutar avanza al paso siguiente; si no, el algoritmo vuelve serialmente, se lanza un proceso para la primera tarea a comenzar desde el paso 1. Cabe destacar que no y ese proceso se encarga de lanzar un proceso para la es necesario calcular p ni q explı́citamente para segunda tarea antes de terminar su ejecución. determinar si N es producto de dos primos. El test de biprimalidad está especificado y probado Cuando una de las funciones distribuidas se ejecuta, en el artı́culo [BF01]. se debe ejectuar en todos los nodos del sistema a la vez. Los nodos trabajan cooperativamente para lograr 4. A partir de N y e se calcula un conjunto de llaves resultados conjuntos utilizando estas funciones. preliminar {d0i }. Estas llaves cumplen que: n X d= d0i 3.2 Módulo del Algoritmo Completo i=1 El módulo del algoritmo completo se encarga de com- El valor d serı́a la llave privada en un sistema RSA poner las funciones principales de los módulos de los simple con el mismo módulo N y el mismo expo- pasos (explicados anteriormente en la sección 3.1) para nente público e. Con este conjunto preliminar no obtener el flujo representado en la figura 1. se puede hacer criptografı́a umbral. Para lograr lo anterior, tiene dos funciones: una 5. Usando el conjunto {d0i }, se calcula el conjunto función auxiliar que se encarga de generar un N can- final de llaves {di }. A diferencia del conjunto didato y una función principal recursiva que imple- preliminar, este conjunto final sı́ permite realizar menta el loop de la figura 1 y el comportamiento que criptografı́a umbral. La técnica que se ocupa para sigue al loop. lograr el comportamiento umbral viene del tra- bajo de Rabin expuesto en el artı́culo [Rab98]. La figura 1 ilustra el orden en el que ocurren los pasos 3.3 Capa de Comunicación del algoritmo. El módulo de comunicación es el que está encargado de administrar toda la comunicación que ocurre entre los nodos y un cliente que es el que solicita la generación de llaves. Se eligió ocupar un modelo de comunicación central en el que toda la comunicación entre nodos es Figure 1: Esquema de los Pasos del Algoritmo vı́a el cliente. Dado lo anterior, este módulo tiene funciones para 3 Detalles de Implementación que los nodos puedan enviar y recibir mensajes y para Luego de especificar el algoritmo implementado, se que el cliente pueda distribuir correctamente los men- procedió a implementar la solución. En esta sección sajes entre los nodos. se describe cómo se llevó a cabo la implementación y La figura 2 explica cómo fluje la comunicación entre algunos detalles particularles del software. procesos y nodos. Figure 2: Flujo de Comunicación entre procesos 1. El proceso a del nodo 1 le quiere enviar un men- saje al proceso b del nodo 2. Ocupa la función send to node, especificando el nodo al que le quiere enviar el mensaje e incluyendo el nombre del proceso destinatario dentro del mensaje. Figure 3: Comparación entre Promedio Obtenido y Promedio Esperado 2. La función le envı́a un mensaje al proceso que está corriendo coord loop en el cliente. 5 Trabajo Futuro 3. El cliente le redirige el mensaje al proceso que • Implementar las optimizaciones del algoritmo está corriendo la función node loop en el nodo propuestas en el artı́culo [BF01]. destinatario. • Agregar una capa de seguridad que cifre el tráfico 4. El proceso de node loop le envı́a el mensaje al de datos entre los nodos. Para esto, lo ideal proceso destinatario, que está indicado dentro del serı́a usar cifrado simétrico (donde todos los nodos mensaje. comparten una llave). Ası́, el cliente se encarga de determinar a qué nodo en- • Probar un esquema distinto de comunicación. tregarle los mensajes y dentro de cada nodo, el proceso que ejecuta la función node loop se encarga de deter- Referencias minar a qué proceso del nodo entregarle los mensajes. [BF01] Dan Boneh and Matthew Franklin. Effi- 4 Resultados cient generation of shared rsa keys. Jour- nal of the ACM (JACM), 48(4):702–722, Primero, se realizaron varias pruebas del algoritmo July 2001. completo para comprobar que estuviera correctamente implementado. Se verificó que todos los nodos llegaran [BOGW88] M. Ben-Or, S. Goldwasser, and al mismo valor de N , que con todas las combinaciones A. Wigderson. Completeness theo- posibles de t llaves privadas se obtuviera el mismo valor rems for non-cryptographic fault tolerant de d y que el valor de d obtenido fuera equivalente al distributed computation. In Proc. STOC, de un sistema RSA normal con módulo N y exponente pages 1–10, 1988. públio e. Además, cuando el tamaño lo permitı́a, se comprobó que el módulo N obtenido fuera producto de [CP05] R. Crandall and C. Pomerance. Prime dos primos. Todas las verificaciones anteriores fueron Numbers: A Computational Perspective, positivas, por lo que se concluyó que la implementación 2nd ed. Springer-Verlag, 2005. del algoritmo está correcta. [Rab98] T. Rabin. A simplified approach to thresh- Además en cada experimento se midió la cantidad old and proactive rsa. In Advances in de intentos de generación de módulo N que se debieron Cryptology — CRYPTO, pages 89–104, realizar. Luego, se calculó el promedio de intentos 1998. agrupados por tamaño de módulo y se comprobó con un valor esperado. Dicho valor esperado se obtuvo del [RSA78] R. L. Rivest, A. Shamir, and L. Adleman. teorema de los números primos [CP05], que indica que A method for obtaining digital signatures se deben realizar en promedio ( 2b ln 2)2 intentos para and public-key cryptosystems. Commun. obtener un módulo biprimo (donde b es el tamaño de- ACM, 21(2):120–126, February 1978. seado del módulo). El gráfico de la Figura 3 muestra el resultado obtenido, donde se puede observar que el promedio de intentos obtenido fue mucho menor al es- perado.