=Paper=
{{Paper
|id=Vol-1727/ssn16-final11
|storemode=property
|title=Implementation of a Distributed Algorithm for Threshold RSA Key Generation
|pdfUrl=https://ceur-ws.org/Vol-1727/ssn16-final11.pdf
|volume=Vol-1727
|authors=Caterina Muñoz
|dblpUrl=https://dblp.org/rec/conf/ssn/Munoz16
}}
==Implementation of a Distributed Algorithm for Threshold RSA Key Generation==
https://ceur-ws.org/Vol-1727/ssn16-final11.pdf
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.