Estrategias de implementación de algoritmos criptográficos post-cuánticos
Abstract
En los últimos años se han producido avances en la computación cuántica para poder elaborar algoritmos criptográficos que sean capaces de soportar y resistir ataques de ordenadores cuánticos. Estos son más potentes que un ordenador normal, ya que podrían explotar las vulnerabilidades de los algoritmos utilizados hoy en día. Estos ordenadores supondrían una amenaza para los algoritmos de cifrado actuales, ya que la velocidad de procesado o computo de estos afecta significativamente a la seguridad que ofrecen, lo que permitiría romper aquellos algoritmos que hasta ahora creíamos que eran muy seguros. El sector de la criptografía post-cuántica está en un crecimiento constante y se espera que en los próximos 10 años estos algoritmos se usen para proteger la información importante del mundo. Como consecuencia, NIST lanzó una convocatoria para elegir varios algoritmos criptográficos que pudiesen ser estandarizados y que pudiesen ser usados en el futuro por las grandes organizaciones para protegersus datos. La selección de estos algoritmos es un proceso que dura mucho tiempo y que consta de distintas fases en las que estos algoritmos son sometidos a distintas pruebas por los expertos de criptografía. En este contexto, en este Trabajo de Fin de Grado, primero, realizamos un análisis de aquellos algoritmos de cifrado que hemos considerado más interesantes dentro de la convocatoria NIST de algoritmos de cifrado post-cuántico. Después, nos centramos en el estudio del algoritmo McEliece, analizando varias implementaciones de dicho algoritmo y realizando un estudio de rendimiento de ellas. Por último, hemos realizado la paralelización de una de las implementaciones del algoritmo para ejecutarlo sobre GPUs, consiguiendo de esta forma una mejora del rendimiento del código.
Full text
Es a egias de implemen ación de algo i mos
c ip og á icos pos -cuán icos
Implemen a ion s a egies o pos -quan um
c yp og aphic algo i hms
TRABAJO FIN DE GRADO
CURSO 2022-2023
AUTORES
PETAR KONSTANTINOV IVANOV Y VÍCTOR MORENO PÉREZ
DIRECTORES
INMACULADA PARDINES LENCE Y MARCOS SÁNCHEZ-ÉLEZ MARTÍN
GRADO EN INGENIERÍA INFORMÁTICA
FACULTAD DE INFORMÁTICA
UNIVERSIDAD COMPLUTENSE DE MADRID
Es a egias de implemen ación de algo i mos
c ip og á icos pos -cuán icos
Implemen a ion s a egies o pos -quan um
c yp og aphic algo i hms
TRABAJO DE FIN DE GRADO EN INGENIERÍA INFORMÁTICA
AUTORES
PETAR KONSTANTINOV IVANOV Y VÍCTOR MORENO PÉREZ
DIRECTORES
INMACULADA PARDINES LENCE Y MARCOS SÁNCHEZ-ÉLEZ MARTÍN
CONVOCATORIA: SEPTIEMBRE DE 2023
GRADO EN INGENIERÍA INFORMÁTICA
FACULTAD DE INFORMÁTICA
UNIVERSIDAD COMPLUTENSE DE MADRID
Resumen
Es a egias de implemen ación de algo i mos c ip og á icos pos -
cuán icos
En los úl imos años se han p oducido a ances en la compu ación cuán ica pa a pode
elabo a algo i mos c ip og á icos que sean capaces de sopo a y esis i a aques de
o denado es cuán icos. Es os son más po en es que un o denado no mal, ya que
pod ían explo a las ulne abilidades de los algo i mos u ilizados hoy en día.
Es os o denado es supond ían una amenaza pa a los algo i mos de ci ado ac uales, ya
que la elocidad de p ocesado o compu o de es os a ec a signi ica i amen e a la
segu idad que o ecen, lo que pe mi i ía ompe aquellos algo i mos que has a aho a
c eíamos que e an muy segu os. El sec o de la c ip og a ía pos -cuán ica es á en un
c ecimien o cons an e y se espe a que en los p óximos 10 años es os algo i mos se usen
pa a p o ege la in o mación impo an e del mundo.
Como consecuencia, NIST lanzó una con oca o ia pa a elegi a ios algo i mos
c ip og á icos que pudiesen se es anda izados y que pudiesen se usados en el u u o
po las g andes o ganizaciones pa a p o ege sus da os. La selección de es os algo i mos
es un p oceso que du a mucho iempo y que cons a de dis in as ases en las que es os
algo i mos son some idos a dis in as p uebas po los expe os de c ip og a ía.
En es e con ex o, en es e T abajo de Fin de G ado, p ime o, ealizamos un análisis de
aquellos algo i mos de ci ado que hemos conside ado más in e esan es den o de la
con oca o ia NIST de algo i mos de ci ado pos -cuán ico. Después, nos cen amos en
el es udio del algo i mo McEliece, analizando a ias implemen aciones de dicho
algo i mo y ealizando un es udio de endimien o de ellas. Po úl imo, hemos ealizado
la pa alelización de una de las implemen aciones del algo i mo pa a ejecu a lo sob e
GPUs, consiguiendo de es a o ma una mejo a del endimien o del código.
Palab as cla e: McEliece, NIST, compu ación cuán ica.
Abs ac
Implemen a ion s a egies o pos -quan um c yp og aphic algo i hms
O e he las yea s, he e ha e been ad ances in quan um compu ing o be able o
de elop c yp og aphic algo i hms ha a e capable o wi hs anding and esis ing a acks
om quan um compu e s. These a e mo e powe ul han no mal compu e s, since hey
could exploi ulne abili ies in algo i hms used oday.
These compu e s would suppose a h ea o cu en c yp og aphic algo i hms, since
hei p ocessing o compu ing speed signi ican ly a ec s he secu i y hey o e . These
would allow b eaking hose algo i hms ha un il now we belie ed we e e y secu e. The
pos -quan um c yp og aphy sec o is cons an ly g owing and i is expec ed ha hese
algo i hms in 10 yea s will be used o p o ec he wo ld's impo an in o ma ion.
Consequen ly, NIST launched a calling signal o choose se e al c yp og aphic algo i hms
ha could be s anda dized and ha could be used in he u u e by la ge o ganiza ions
o p o ec hei da a. The selec ion o hese algo i hms is a ime-consuming p ocess ha
consis s o di e en phases in which hese algo i hms a e pu down o di e en es s by
c yp og aphy expe s.
In his con ex , in his Final Deg ee P ojec , i s , we ca y ou an analysis o hose
c yp og aphic algo i hms ha we ha e conside ed mos in e es ing wi hin he NIST
signal call o pos -quan um c yp og aphic algo i hms. A e wa ds, we ocus on he
s udy o he McEliece algo i hm, analyzing se e al implemen a ions o i and ca ying
ou a pe o mance s udy o hem. Finally, we ha e pa allelized one o he
implemen a ions o he algo i hm o un i on GPUs, hus imp o ing he pe o mance o
he code.
Keywo ds: McEliece, NIST, quan um compu ing.
ÍNDICE
1.INTRODUCCIÓN ............................................................................................................. 1
1.1. Mo i ación ............................................................................................................. 1
1.2. Obje i os ................................................................................................................ 2
1.3 Plani icación ............................................................................................................ 2
1.4. Es ado del a e ....................................................................................................... 4
1.5. Es uc u a de la memo ia ...................................................................................... 5
1.INTRODUCTION ............................................................................................................. 7
1.1. Mo i a ion.............................................................................................................. 7
1.2. Objec i es .............................................................................................................. 8
1.3 Plani ica ion ............................................................................................................ 8
1.4. S a e o he a ..................................................................................................... 10
1.5. Memo y s uc u e ................................................................................................ 11
2. P oceso de es anda ización PQC de NIST ................................................................... 13
2.1. Algo i mo pos -cuán ico SIKE (Supe singula Isogeny Key Encapsula ion) ......... 14
2.2. Algo i mo pos -cuán ico BIKE (Bi Flipping Key Encapsula ion) .......................... 15
2.3. Algo i mo pos -cuán ico Classic McEliece ........................................................... 16
2.4. Algo i mo pos -cuán ico HQC (Hamming Quasi-Cyclic) ...................................... 16
2.5. Finalis as de la e ce a onda del concu so ......................................................... 17
2.5.1 CRYSTALS-Kybe ............................................................................................. 17
2.5.2. NTRU .............................................................................................................. 18
2.5.3. SABER ............................................................................................................ 19
3.IMPLEMENTACIONES ................................................................................................... 20
3.1. C y OpenACC ........................................................................................................ 20
3.2. Códigos bina ios de Goppa .................................................................................. 21
3.3. Es uc u a códigos es udiados ............................................................................. 23
3.4. Implemen ación seleccionada ............................................................................. 26
3.4.1. Bina yTex .h y Bina yTex .c ........................................................................... 41
3.4.2. Tex Bina y.h y Tex Bina y.c ........................................................................... 42
3.4.3. Dec yp .c ....................................................................................................... 43
3.4.4. Enc yp .c ........................................................................................................ 44
3.4.5. key_gen.c....................................................................................................... 45
3.4.6. ma ix.h y ma ix.c ........................................................................................ 46
3.4.7. mceliece.h y mceliece.c ................................................................................. 62
3.4.8. qc_mdpc.h y qc_mdpc.c ................................................................................ 65
3.4.9. u ili y.h y u ili y.c ........................................................................................... 73
4.Implemen ación ealizada ........................................................................................... 74
4.1. P ime a onda de mejo as ................................................................................... 74
4.1.1. ma ix.c .......................................................................................................... 75
4.1.2. qc_mdpc.c ..................................................................................................... 89
4.2. Segunda onda de mejo as .................................................................................. 94
4.2.1. ma ix.c .......................................................................................................... 94
4.2.2. qc_mdpc.c ..................................................................................................... 96
5. Resul ados ................................................................................................................ 102
5.1 Resul ados ob enidos con las dis in as e siones ........................................... 102
5.2. O as in es igaciones ..................................................................................... 104
5.3. Compa aciones adicionales ........................................................................... 107
6.Apo aciones y Conclusiones ..................................................................................... 110
6.1. Apo aciones ...................................................................................................... 110
6.2. Conclusiones ...................................................................................................... 111
6.3. Obje i os u u os ............................................................................................... 112
6. Con ibu ions and Conclusions ................................................................................. 113
6.1. Con ibu ions ..................................................................................................... 113
6.2. Conclusions ........................................................................................................ 114
6.3. Fu u e Objec i es ............................................................................................... 115
Bibliog a ía .................................................................................................................... 116
1
1.INTRODUCCIÓN
1.1. Mo i ación
La segu idad in o má ica es el á ea enca gada de ga an iza la con idencialidad y la
in eg idad de la in o mación y el co ec o uncionamien o de las in aes uc u as
in o má icas. El uso de las ecnologías de la in o mación y de las comunicaciones es cada
ez mayo y el núme o de cibe a aques c ece exponencialmen e. El pode llega a
e ela , co ompe o incluso modi ica cie a in o mación de e ce os puede ene
g a es consecuencias, po lo que ene una buena segu idad es imp escindible en
cualquie sis ema in o má ico. Como consecuencia la segu idad in o má ica se ha
con e ido en uno de los p incipales e os de hoy en día pa a las emp esas,
o ganizaciones y gobie nos.
La c ip og a ía es la ciencia enca gada de es udia las dis in as écnicas usadas pa a
ans o ma (ci a ) la in o mación con el obje i o de hace la i econocible a ecep o es
no au o izados. Po lo an o, es una pa e muy impo an e de la segu idad in o má ica.
El obje i o de la c ip og a ía es p o ege la in o mación, ci ándola, y que solo el
des ina a io de la in o mación sea capaz de ecupe a (desci a ) la in o mación o iginal.
Pe o como odos sabemos, no hay nada segu o al 100% y hay algo i mos y mecanismos
que pueden in en a desci a la in o mación sin conoce la cla e necesa ia pa a hace lo.
En onces, es muy impo an e usa algo i mos de ci ado que sean obus os, es deci ,
muy di íciles de “ ompe ”.
La in eg idad de la in o mación es uno de los pila es undamen ales, que jun o a la
con idencialidad y la disponibilidad o man la conocida iada CIA. Es impo an e a la
ho a de ga an iza la p ecisión y alidez de la in o mación e i a cualquie modi icación
sob e ellas no au o izada o no in encionada. Pa a man ene la in eg idad de los da os,
se u ilizan écnicas como el uso de i mas digi ales, el con ol de e siones y los con oles
de cambios.
P e iendo el a ance de la compu ación cuán ica en el u u o es necesa io busca nue os
algo i mos esis en es a es e ipo de compu ación. Su ge así la con oca o ia del NIST
pa a busca algo i mos pos cuán icos de i ma digi al y de in e cambio de cla e segu os.
En e los algo i mos de ci ado pos -cuán icos que nos p opusie on es udia se
encon aban el SIKE, el BIKE, el HQC y el McEliece. Es os algo i mos o man pa e de la
cua a onda de NIST pa a encon a algo i mos de ci ado de cla e pública con el
p opósi o an e io men e mencionado. Es a onda se lanzó en el año 2022 y concluyó en
oc ub e de 2022 que ue cuando e minaba el iempo pa a adjun a las modi icaciones
de aquellos seleccionados. Es os son los algo i mos que siguen oda ía en la
compe ición. Sin emba go, NIST lanzó es e concu so en el e ano de 2016 y 7 años más
a de y cua o ondas después, oda ía se siguen buscando algo i mos que sean capaces
de lucha con a los o denado es cuán icos.
2
T as ealiza un ex ensi o es udio de los algo i mos p opues os, hemos ido desca ando
algunos de ellos has a queda nos inalmen e solo con el algo i mo de McEliece.
Desca amos el algo i mo SIKE po que un o denado single-co e [1] lo consiguió ompe
en una ho a. En cuan o al algo i mo BIKE, su implemen ación es á en VHDL y es e
lenguaje no esul a adecuado pa a los obje i os buscados en es e abajo. También
desca amos el algo i mo HQC, po que la can idad de in o mación publicada sob e él es
escasa, lo que complicaba nues a in es igación.
Finalmen e, el algo i mo de ci ado pos -cuán ico McEliece acabó siendo nues a opción
de ini i a ya que o mó pa e de la e ce a onda y ue uno de los inalis as de la úl ima
ase de es a onda. Además, ue nues a p incipal opción desde el p incipio, debido a la
g an can idad de in o mación publicada y a la g an a iedad de implemen aciones
encon adas en dis in os lenguajes de p og amación.
1.2. Obje i os
A con inuación, p esen amos los obje i os en los que pond emos nues o oco en el
es udio y ealización del p esen e T abajo de Fin de G ado:
• Implemen a de o ma pa alela uno de los algo i mos inalis as de la
con oca o ia del Na ional Ins i u e o S anda s and Technology de Es ados
Unidos (NIST).
• Analiza desde un pun o de is a uncional y de implemen ación los algo i mos
inalis as de la con oca o ia NIST con especial én asis en aquel que conside emos
que iene más posibilidades de se pa alelizado.
• Comp ende la amenaza que supone la compu ación cuán ica, y la c ip og a ía
pos -cuán ica como u u a solución a la exposición de la segu idad in o má ica a
se cada ez más ulne able.
• Analiza y compa a el endimien o de las dis in as implemen aciones buscadas
y es udiadas an e io men e.
• Modi ica el código pa a que ome mensajes po consola y los con ie a a bina io
pa a su pos e io ci ado y desci ado (en la implemen ación o iginal e an
mensajes p ede inidos en bina io de un amaño es ánda ).
1.3 Plani icación
En es e apa ado expond emos una b e e abla con aquello que hemos ido ealizando
po e apas, a es o se le debe ía de ag ega la lec u a y ac ualización de in o mación ya
que el p oceso NIST sigue igen e.
07/09/2022-10/10/2022
3
Se analizó la documen ación p opo cionada po los
u o es sob e la amenaza de la compu ación cuán ica y
sob e la c ip og a ía pos -cuán ica.
Se ealizó una pequeña in es igación sob e los cua o
inalis as de la cua a onda del concu so de NIST y se
p ocedió a ealiza un pequeño documen o con
in o mación sob e los algo i mos SIKE, BIKE, HQC y Classic
McEliece. Además, se seleccionó el algo i mo Classic
McEliece después de consul a lo con los u o es debido a
la abundan e in o mación disponible sob e él.
11/10/2022- 23/1/2023
Se ealizó una búsqueda in ensi a pa a encon a las
mejo es implemen aciones posibles del algo i mo pos -
cuán ico de Classic McEliece. Al inal se encon a on es
implemen aciones óp imas de es e algo i mo en
eposi o ios Gi Hub pa a abaja con ellas.
Se comenzó con la ecopilación de in o mación y el p ime
bo ado de la memo ia ealizando una p ime a e sión
del esumen, la mo i ación, los obje i os del abajo de in
de g ado y la explicación de los lenguajes de
p og amación u ilizados pa a la implemen ación.
Se comp obó que las implemen aciones de los algo i mos
uncionaban de o ma co ec a y se hizo un es udio del
código pa a la comp ensión de su uncionamien o.
24/1/2023 – 26/3/2023
Se ealiza on mejo as sob e la implemen ación añadiendo
la posibilidad de in oduci mensajes en o ma o ex o
que pos e io men e se án aducidos a o ma o bina io
pa a pode ealiza la ejecución del ci ado.
Se ealiza on co ecciones sob e el código de la
implemen ación y se añadió una nue a unción que
ellena de o ma au omá ica con ce os, cuya inalidad es
comple a el ex o pa a que sea múl iplo de 8.
Se cambió el en o no de abajo a GoogleColab que
pe mi e es ablece un emulado de GPU pa a pode
ejecu a las nue as pa es del código ealizadas en
lenguaje Open ACC pa a pode ejecu a de o ma pa alela
la ejecución.
Po úl imo, se c eó un eposi o io de Gi Hub donde se han
subido las e siones de la implemen ación.
27/3/2023 - 15/5/2023
Se esc ibió in o mación de allada sob e el algo i mo SIKE
y se explicó po que se decidió desca a lo. Se co igie on
10
unc ions o each ile and wha each ile is o . In addi ion,
igu es we e added o g ea e unde s anding since he e
a e many unc ions and names.
A e wa ds, ables we e added wi h he ime compa isons
and i was speci ied wha has been pa allelized and why
i s pa alleliza ion has been ca ied ou .
20/6/2023 -18/7/2023
New imp o emen s we e made o he selec ed
implemen a ion. In addi ion, mo e in o ma ion on he
esea ch ca ied ou on he selec ed algo i hms was
added and he wo ding o he memo y was e ined.
18/7/2023 - 4/9/2023
RSA and DH sc ip s we e made using OpenSSL o
compa ison wi h ou implemen a ions. In addi ion,
memo y co ec ions we e made, bibliog aphic ci a ions
we e added and de ails we e inalized. In addi ion, he
sec ions ha emained o be comple ed we e w i en.
1.4. S a e o he a
Nowadays RSA is one o he mos used enc yp ion algo i hms o digi al signa u es. RSA
algo i hm was de eloped in 1977 by Ri es , Shami and Adleman. I s secu i y lies in he
complexi y o ac o ing in ege s, since i s ope a ion is based on making he p oduc o
wo p ime numbe s chosen a andom and kep sec e . Finding hese wo numbe s om
i s p oduc is oo expensi e o classical compu e s. Fu he mo e, he size o he wo
p ime numbe s becomes la ge as he compu ing powe o compu e s inc eases.
Howe e , sol ing his p oblem will no longe be impossible o quan um compu e s
since Sho 's algo i hm can ac o ize an in ege in polynomial ime. F om all his a ises
he need o look o new, mo e esis an algo i hms. Ano he algo i hm ha will be
ulne able o quan um compu ing is he Di ie-Hellman algo i hm, which is used o
symme ic key exchange and is based on disc e e algo i hms. The Di ie-Hellman
algo i hm allows wo pa s o secu ely ag ee on a sec e key. The sec e key does no
a el, bu a he he wo pa s end up gene a ing he same key. To unde s and his,
le 's ake a e y simple example:
• We ha e wo compu e s: a compu e A has he colo ed as a sec e key and
ano he compu e B has he colo blue.
• Bo h compu e s ag ee o ha e he colo yellow as a mix ( his colo will be mixed
wi h each o he 's p i a e keys).
• So when mixing, compu e A would ha e an o ange colo and compu e B would
ha e a g een colo .
11
• Now bo h compu e s send he new colo hey ha e gene a ed o he o he so
ha he p ocess o c ea ing he sec e key can con inue.
• They hen mix he ecei ed colo wi h hei sec e key and his esul ing colo
would be he common sec e key.
I is also impo an o men ion he use o he DSA algo i hm o gene a ing digi al
signa u es, which is a s anda d o he Fede al Go e nmen o he Uni ed S a es o
Ame ica. The DSA algo i hm was made public on Augus 30, 1991. I is a pu ely
asymme ic algo i hm, jus like RSA. This algo i hm is used o sign, bu no o enc yp
in o ma ion. A disad an age o his algo i hm is ha i equi es much mo e compu ing
ime han RSA.
The ques ion o whe he c yp og aphy will no esis u u e a acks a ose a ew yea s
ago. A icles om 2009 can be ound ques ioning whe he cu en algo i hms would be
able o wi hs and he a acks o a u u e quan um compu e and explaining ha , soon
he applica ion o Sho 's algo i hm, which is an algo i hm capable o ac o ing a numbe
N e icien ly, om a mo e powe ul compu e will pose a g ea h ea o c yp og aphy.
1.5. Memo y s uc u e
Ou memo y has been s uc u ed in o six chap e s, which we will b ie ly desc ibe below.
In he In oduc ion chap e , he mo i a ions, objec i es, memo y s uc u e and s a e o
he a a e men ioned, hus desc ibing bo h he p oblem o be sol ed and he cu en
s a e o enc yp ion algo i hms.
The second chap e explains how he con es o choose he bes pos -quan um
algo i hms by NIST came abou and how many ounds ha e been ca ied ou o da e.
Subsequen ly, he inalis algo i hms o he ou h ound a e de ined, explaining how
hey wo k and why we ha e disca ded he SIKE, BIKE and HQC algo i hms. Finally, he
inalis algo i hms o he hi d ound o he con es a e desc ibed, excep o he Classic
McEliece ha we ha e explained in a sepa a e sec ion. We analyze how hese algo i hms
wo k and men ion hei ad an ages and disad an ages.
In he hi d chap e we explain which p og amming languages ha e been used. In
addi ion, we ha e added a b ie ma hema ical explana ion o he Goppa bina y codes
used in he ope a ion o he McEliece enc yp ion algo i hm and we explain how he
ound implemen a ions a e s uc u ed. We also show a able wi h he execu ion imes
o each o hese implemen a ions.
In he ou h chap e we desc ibe p ecisely he iles ha make up he implemen a ion
wi h which we ha e decided o wo k and he unc ions ha compose hem. We ha e
also made a pe o mance imp o emen by pa allelizing he implemen a ion o be able
o un i on GPU and explain how and why hey can be pa allelized. In addi ion, we ha e
added a compa a i e able wi h he execu ion imes be o e and a e making he
imp o emen s in he code.
12
In he i h chap e , we explain how ou implemen a ions a e execu ed and we make a
compa ison be ween hem. In addi ion, we d aw in o ma ion om o he McEliece
in es iga ions. And we end he chap e by compa ing he unpa allelized e sion and ou
second pa allelized e sion wi h he RSA and Di ie-Hellman (DH) algo i hms o ob ain a
iew o he imes o each algo i hm.
And inally, a six h chap e in which we desc ibe ou con ibu ions o his wo k, he
objec i es achie ed and he main conclusions ha can be d awn.
13
2. P oceso de es anda ización PQC de NIST
El Ins i u o Nacional de Es ánda es y Tecnología de EE. UU. (NIST) [3] ha iniciado un
p oceso pa a solici a , e alua y es anda iza uno o más algo i mos de c ip og a ía de
cla e pública esis en es a la compu ación cuán ica. Ac ualmen e, los algo i mos de
ci ado de cla e pública se especi ican en el es ánda de i ma digi al (FIPS 186-4), en la
ecomendación pa a esquemas de es ablecimien o de cla es po pa es u ilizando
ci ados de loga i mo disc e o (SP 800-56A Re isión 2) y en la ecomendación pa a
esquemas de es ablecimien o de cla es po pa es u ilizando ci ados de ac o ización de
en e os (SP 800-56B Re isión 1). Sin emba go, es os algo i mos son ulne ables a
u u os a aques de compu ado as cuán icas a g an escala. Los o denado es hoy en día
no ienen su icien e capacidad pa a ompe los algo i mos de ci ados clásicos ac uales
y los algo i mos de i ma digi al, pe o la si uación puede cambia en los p óximos años
y es necesa io p epa a la base pa a la ans e encia de c ip osis emas a nue os
es ánda es.
Se p e ende que los nue os es ánda es de ci ado de cla e pública especi iquen uno o
más algo i mos adicionales de i ma digi al no clasi icada y di ulgada públicamen e,
ci ado de cla e pública y es ablecimien o de cla es que es én disponibles en odo el
mundo y sean capaces de p o ege la in o mación con idencial en un u u o p e isible,
incluso después de la llegada de las compu ado as cuán icas.
El concu so se inició en el año 2016 con el p oceso de es anda ización PQC (Pos -
Quan um C yp og aphy S anda diza ion P ocess). Tiene como obje i o elegi algo i mos
de ci ado pos -cuán ico adecuados pa a su p omoción como es ánda es. Los
algo i mos p opues os, 23 algo i mos de i ma digi al y 59 algo i mos de ci ado con
dis in as ap oximaciones, ue on analizados po expe os independien es en busca de
posibles ulne abilidades y debilidades.
El 15 de julio de 2022 hubo una nue a onda sob e algo i mos uni e sales de ci ado
pos -cuán ico. En e los inalis as se encon aba el algo i mo de McEliece, que aún no
se es anda iza ía debido al g an amaño de su cla e pública.
El concu so has a aho a ha ealizado un o al de 4 ondas. Una onda suele du a en e
12 y 18 meses, aho a mismo el concu so se encuen a en la onda 4 donde compi en los
algo i mos BIKE, McEliece y HQC, basados en código, y po o a pa e el algo i mo SIKE,
basado en isogenia de la cu a elíp ica supe singula . En la onda 3 el ganado ue
CRYSTALS-Kybe [4] que ganó a NTRU po que es e algo i mo gene aba las cla es
len amen e y enía cla es públicas y ex os ci ados muy la gos. El cos e o al de la
gene ación de las cla es en NTRU es un 30% supe io al de Kybe , lo que hace imposible
su implemen ación en disposi i os limi ados, es deci , en disposi i os con unos ecu sos
limi ados. O o de los inalis as ue el algo i mo SABER, que enía el cos e más bajo
g acias a sus cla es públicas y a sus ex os ci ados de pequeño amaño. Es o le pe mi ió
compe i con Kybe , ya que al igual que es e algo i mo se puede implemen a en
disposi i os limi ados. SABER pe dió simplemen e po que Kybe e a el núme o uno en
14
odos los benchma ks y p uebas ealizadas. El úl imo inalis a de la onda 3 ue Classic
McEliece, que enía un endimien o di e en e espec o a los o os inalis as po lo que
no ue compa ado di ec amen e con el endimien o del es o. U iliza cla es públicas y
p i adas g andes pe o la elocidad de su ci ado y desci ado y el pequeño amaño de
sus ex os de ci ado lo man u ie on a la pa con el es o, po ello es e algo i mo puede
o ece el mejo endimien o en aplicaciones donde no se iene en cuen a la gene ación
de las cla es en el cos e o al. Es e algo i mo es unos de los pa icipan es de la onda 4
anunciados en julio de 2022.
2.1. Algo i mo pos -cuán ico SIKE (Supe singula
Isogeny Key Encapsula ion)
SIKE [5] es un algo i mo pos -cuán ico pa a es ablece una cla e sec e a en e dos pa es
a a és de un canal de comunicaciones no con iable. Es e algo i mo es análogo al
in e cambio de cla es de Di ie-Hellman, pe o se basa en eco idos en un g a o de
isogenia supe singula y ue diseñado pa a esis i el a aque c ip oanalí ico de un
a acan e en posesión de una compu ado a cuán ica. Cuen a con una de las cla es de
ci ado con meno amaño en e los algo i mos pos -cuán icos, sus cla es públicas son
de 2688 bi s y su ni el de segu idad cuán ica de 128 bi s. P opo ciona sec e o pe ec o
hacia adelan e pa a e i a que las cla es comp ome idas ulne en con idencialidad de
u u as sesiones, es deci que, en el caso de que se descub a la cla e p i ada, oda la
in o mación compa ida en el u u o es a ía lib e del pelig o de se descubie a. Es e
algo i mo es el p incipal candida o pa a sus i ui al algo i mo Di ie-Hellman e íme o y
al algo i mo de cu a elíp ica Di ie-Hellman e íme o.
SIKE iene como en aja p incipal el pequeño amaño de sus cla es compa ándolo con
o as p imi i as que o ecen una segu idad cuán ica azonable. Las cla es públicas que
es án sin comp imi pueden se de dis in os amaños, como las e siones de 330 y 378
by es que se compa an con el módulo de 384 by es que o ece una segu idad clásica de
128 bi s. Po o o lado, es án los modelos de mayo amaño con cla es de 462 by es y
564 by es espec i amen e, con ex os de ci ado de 596 by es. Se ha p opues o una
mejo a sob e la úl ima e sión que pe mi e comp imi aún más las cla es públicas, de
al mane a que o ece una mejo a gene al de un 60% de su amaño o iginal. Además, se
mejo a el endimien o de un 139% a un 160% du an e la gene ación de las cla es
públicas, del 66% al 90% du an e el ci ado y del 59% al 68% du an e el desci ado.
Po o o lado, o a en aja de es e algo i mo es que en las lib e ías que usa se encuen a
odo lo necesa io pa a implemen a de o ma segu a la cu a elíp ica de Di ie-Hellman
con un esquema híb ido de in e cambio de cla es con un cos e mínimo de
p og amación. Sin emba go, espec o a los o os candida os, la p incipal des en aja de
SIKE es que es de los algo i mos de peo endimien o.
15
La azón po la que decidimos desca a es e algo i mo ue po que se consiguió ompe
usando un o denado con un solo núcleo. Los in es igado es del g upo de Segu idad
In o má ica de C ip og a ía Indus ial de KU Leu en acaba on con el algo i mo a acando
la ma emá ica en la que se basaba su diseño en ez de in en a ompe su segu idad
buscando ulne abilidades en su código. U iliza on el eo ema de Glue and Spli , al que
el algo i mo SIDH (simila al SIKE) es ulne able. Es e algo i mo usa cu as de géne o 2
pa a a aca las cu as elíp icas. El c eado del algo i mo, Da id Jao, salió en su de ensa
a i mando que sus c ip óg a os son especialis as en ma emá icas pu as y no se
espe aban es os esul ados. Sin emba go, es o supone un g a e p oblema de segu idad,
ya que demues a que se puede ompe con un simple o denado y su icien e
conocimien o de las ma emá icas en las que se basa el algo i mo.
2.2. Algo i mo pos -cuán ico BIKE (Bi Flipping Key
Encapsula ion)
BIKE [6] [7] es un KEM (Key Encapsula ion P o ocol) basado en QC-MDPC (Quasi-Cyclic
Mode a e Densi y Pa i y-Check), que puede se ácilmen e desci ado median e écnicas
basadas en in e cambios de bi s. Fue diseñado o iginalmen e pa a p o ocolos de
comunicación sínc ona (como TLS) con cla es e íme as. Solo debe ía es a pe mi ido
desci a una única ez con una cla e p i ada dada, lo que hace que p opo cione sec e o
pe ec o hacia delan e. La eu ilización de cla es o adap ación a p o ocolos de
comunicación asínc ona, como puede se el caso de Gmail, equie e u iliza cla es
es á icas de la ga du ación, que no ga an izan el sec e o pe ec o hacia delan e.
Lo mencionado an e io men e lle a a dos conclusiones. La p ime a, que es inmune a los
a aques de eacción GJS, ya que es os a aques necesi an obse a una g an can idad de
ex os desci ados pa a una misma cla e p i ada (algo que es imposible si es án siendo
u ilizadas cla es e íme as). Y la o a es que la gene ación de las cla es debe se e icien e
debido a que se ealiza en cada encapsulación de cla es. Podemos e los amaños de
las cla es en la Tabla 1.
La segu idad IND-CPA es alcanzada pa a BIKE si los pa áme os son escogidos de mane a
que los p oblemas compu acionales subyacen es gené icos cuasi-cíclicos basados en
código son lo su icien emen e di íciles. Es deci , si los posibles a acan es no pueden
dis ingui en e los ci ados de dos mensajes a su elección.
La segu idad IND-CCA es alcanzada pa a BIKE si BIKE es ins anciado con un desci ado
que enga un DFR (Decoding Failu e Ra e). IND-CCA es un modelo de a aque de
c ip oanálisis que pe mi e ecoge in o mación median e la ob ención de los ex os
desci ados a pa i de ex os ci ados elegidos.
16
TAMAÑO
NIVEL 1
NIVEL 3
NIVEL 5
Cla e P i ada
l+w *[𝑙𝑜𝑔2(𝑟)]
2,244
3,346
4,640
Cla e Pública
12,323
24,659
40,973
Tex o Ci ado
+ l
12,579
24,915
41,229
Tabla 1: Tamaños mínimos de la cla e pública, de la cla e p i ada y del ex o a ci a en bi s eque idos po el
algo i mo BIKE
2.3. Algo i mo pos -cuán ico Classic McEliece
Classic McEliece [8] [9]Es un algo i mo de ci ado asimé ico c eado en 1978 po Robe
McEliece, que ue el p ime o en u iliza alea o ización en el p oceso de ci ado. Se
conside a un algo i mo pos -cuán ico ya que es capaz de esis i a aques que u ilizan el
algo i mo Sho y su segu idad se basa en la du eza de la decodi icación de un código
lineal gene al.
Pa a la desc ipción de la cla e p i ada se usa un código de co ección de e o es pa a el
que se conoce un algo i mo de decodi icación capaz de co egi un núme o ini o de
e o es. U iliza códigos de Goppa que se pueden decodi ica de mane a e icien e con un
algo i mo de Pa e son. La cla e pública se de i a de la p i ada cub iendo el código
seleccionado como código gene al, pa a ello la ma iz gene ado a del código es
pe u bada po dos ma ices in e ibles al aza . Los a aques más e ec i os con a es e
algo i mo son a aques que usan algo i mos de decodi icación de conjun os de
in o mación. Respec o al RSA es e algo i mo o ece un ci ado y desci ado más ápido,
y ambién se puede usa pa a gene a cons ui i mas. Una de sus des en ajas es el uso
de ma ices de g an amaño pa a las cla es pública y p i ada.
Los a aques de ue za b u a no ienen éxi o ya que los algo i mos pa a decodi ica el
conjun o de la in o mación ienen un iempo de ejecución exponencial. Los a aques
es uc u ales son más e icaces, pe o al usa códigos Goppa son más esis en es y
pe sis en es a la ho a de se decodi icados. McEliece sugi ió o iginalmen e amaños de
pa áme os de segu idad de n=1024, k=524, =50 dando como esul ado un amaño de
cla e pública de 524*(1024−524) = 262.000 bi s.
En conclusión, la en aja más impo an e del McEliece es la segu idad. Sin emba go, la
e iciencia, conc e amen e en la gene ación de cla es, no es su pun o ue e. Pa a ello,
las aplicaciones que lo usen deben aumen a el iempo de ida de dichas cla es pa a
educi el cos e de gene a y dis ibui las cla es. El ci ado y el desci ado son
azonablemen e ápidos en so wa e e imp esionan emen e ápidos en ha dwa e.
2.4. Algo i mo pos -cuán ico HQC (Hamming Quasi-
Cyclic)
17
HQC [10] Es un esquema de ci ado de cla e pública basado en un código diseñado pa a
p opo ciona segu idad con a a aques de compu ado as clásicas y cuán icas. O ece un
amaño de cla es más g ande que el clásico McEliece. P o ee un análisis de allado de la
p obabilidad de allo del ci ado, lo que hace posible elegi pa áme os que
p obablemen e e i en a aques eac i os que comp ome en la segu idad de los
esquemas de segu idad del QC-LDPC y QC-MDPC. Es o lo con ie e en uno de los
mejo es candida os en el p oceso de es anda ización del NIST de algo i mos de ci ado
pos -cuán icos. Es e algo i mo iene una es uc u a especí ica que pe mi e ab i la
pue a a cie os a aques especí icos es uc u ales [11]. El p ime a aque gené ico es el
a aque DOOM, que debido a la ciclicidad implica una ganancia de O (√ n). También es
posible conside a a aques a la o ma del polinomio que gene a la es uc u a cíclica.
Es os a aques son especialmen e e icaces cuando el polinomio X^(n-1) iene muchos
ac o es de bajo g ado. HQC usa dos ipos de código: uno decodi icable que es capaz de
co egi un núme o de e minado de e o es a a és de un algo i mo e icien e de C y
o o código de doble ci culación alea o ia con una ma iz de comp obación. En la Figu a
1 pod emos e un ejemplo simpli icado de su uncionamien o.
Figu a 1: Esquema de ejemplo uncionamien o HQC.
2.5. Finalis as de la e ce a onda del concu so
La e ce a onda del concu so de NIST pa a encon a algo i mos pos -cuán icos inalizó
en julio de 2022 y en ella se selecciona on cua o algo i mos esis en es, que an o los
o denado es con encionales como los cuán icos debe ían de ene di icul ades pa a
ompe . Los algo i mos es án diseñados pa a dos a eas p incipales pa a las que
no malmen e se u iliza el ci ado: ci ado gene al, u ilizado pa a p o ege la in o mación
in e cambiada a a és de una ed pública; y i mas digi ales, u ilizadas pa a la
au en icación de iden idad. Es os algo i mos inalis as ue on: Classic McEliece,
CRYSTALS-Kybe , NTRU y SABER.
2.5.1 CRYSTALS-Kybe
El algo i mo pos -cuán ico CRYSTALS-Kybe [12] ue unos de los inalis as y
pos e io men e ganado de la e ce a onda del concu so NIST. Ha sido seleccionado
18
pa a que pueda se es anda izado pa a el ci ado con la inalidad de p o ege la
in o mación de a aques de o denado es cuán icos. Kybe u iliza un sis ema de ci ado
basado en cla es públicas, cuyo uso p incipal es es ablece sis emas de cla es simé icas
u ilizando p o ocolos de al o ni el como TLS, Signal o OpenPGP. El algo i mo iene es
ni eles de segu idad y los amaños de las cla es son simila es a los amaños de las cla es
del algo i mo RSA.
Al se un algo i mo que u iliza cla es públicas y p i adas, pa a pode ealiza el ci ado y
desci ado, se necesi an ope aciones de polinomios y un módulo q. Pa a la gene ación
de la cla e p i ada se necesi an dos polinomios con pequeños coe icien es y pa a la
gene ación de la cla e pública se necesi an dos elemen os: Una ma iz de polinomios
alea o ios y un ec o de polinomios que necesi a un ec o adicional de e o es. Es e
p oceso de gene ación de cla es pe mi e que sea casi imposible ecupe a la cla e
p i ada ya que el algo i mo u iliza el módulo de ap endizaje con e o es.
El p oceso de ci ado u iliza un e o y un ec o de núme os alea o ios. Cada uno de
esos ec o es se c ean desde ce o pa a cada ci ado que se a a ealiza . Pa a ci a el
mensaje hay que con e i lo en un polinomio. Es o se hace u ilizando la o ma bina ia
del mensaje, cada bi del mensaje se usa como coe icien e, y luego hay que escala el
polinomio. En el p oceso de desci ado, p ime o, se necesi a c ea un esul ado “noisy”,
es o quie e deci que no iene ninguna impo ancia. Es o es debido a que después de
ealiza la c eación de ese esul ado, se emplea la cla e p i ada pa a desci a el ex o
ci ado y ecupe a el ex o o iginal.
Kybe es un sis ema de ci ado de ipo que u iliza el sis ema de módulo de ap endizaje
con e o es, es o pe mi e que el p oceso de desci ado sea un p oceso bas an e
complicado de a e igua pa a los o denado es cuán icos. Es deci , es complicado de
e e i el p oceso aplicado pa a gene a las cla es y consegui ob ene así la cla e
p i ada. Es un algo i mo que iene las en ajas de los algo i mos basados en celosías,
en e las que des aca la apidez.
2.5.2. NTRU
NTRU [13]es un algo i mo pos -cuán ico inalis a de la e ce a onda del concu so de
NIST. U iliza c ip og a ía basada en celosía pa a ci a y desci a da os y es esis en e a
los a aques que u ilizan el algo i mo de Sho .
Es e algo i mo ealiza ope aciones de cla e p i ada mucho más cos osas y ápidas que
el algo i mo RSA. Es e algo i mo no es ulne able a a aques de o denado es cuán icos
como lo son el RSA y la c ip og a ía de cu a elíp ica.
La segu idad del algo i mo p ocede de la in e acción del sis ema de c uce de polinomios
con la educción de independencia de los módulos p y q. En el amewo k del algo i mo,
su ci ado u iliza un elemen o alea o io que pe mi e que cada mensaje enga a iedad
de ci ados. El ci ado, el desci ado y la c eación de las cla es son ope aciones áciles,
ápidas y sencillas. Se usan ope aciones cuad á icas pa a ealiza el ci ado y el
desci ado de mensajes de longi ud N, haciéndolo mucho más ápido que las
19
ope aciones cúbicas que equie e el algo i mo RSA. Las cla es ienen una longi ud lineal
que esul a se bas an e buena en compa ación con las cla es cuad á icas de o os
algo i mos ápidos como el McEliece.
2.5.3. SABER
SABER [14] es un algo i mo pos -cuán ico que ue inalis a en la e ce a onda del
concu so de NIST. Es e algo i mo u iliza el mecanismo de ci ado de cla es más conocido
como KEM, que o ece un mé odo e icien e de ans e encia de mensajes de g an
amaño con las en ajas de las cla es públicas. También simpli ica el p oceso de ci ado
al gene a un elemen o alea o io en un g upo ini o que p opo ciona la cla e simé ica
c eando un hash del elemen o alea o io.
La segu idad de SABER depende de la du eza del p oblema del módulo de ap endizaje
con edondeo que lo p o ege con a los o denado es cuán icos. Es e algo i mo es á
o mado po es ni eles que son Ligh SABER, SABER y Fi eSABER. Los p incipales
bloques a i mé icos consis en en mul iplicaciones de polinomios, ope aciones bi a bi y
ope aciones en ejadas. Los módulos de núme os en e os son cuad á icos po lo que no
hace al a u iliza módulos de educción con ope aciones bi a bi .
SABER se cons i uye de los algo i mos Sabe .PKE y Sabe .KEM. Sabe .PKE es el esquema
de ci ado de la cla e pública de segu idad IND-CPA. Y a pa i de es e, usando una
e sión de la ans o mada de Fujisaki-Okamo o, su gió Sabe . KEM que es el mecanismo
de encapsulación de la cla e de segu idad IND-CCA en el que as su gene ación las
cla es públicas y p i adas se de uel en en dos a ays sepa ados po un by e pa a que
puedan se u ilizadas en las ope aciones de ci ado y desci ado. La ope ación de ci ado
coge la cla e pública y gene a unas cla es de sesión y el ex o ci ado u ilizando la semilla
de la cla e de sesión y el p oceso de desci ado coge el ex o ci ado y la cla e p i ada y
ecupe a la cla e de sesión que pe enece al ex o ci ado.
El algo i mo puede ene allos como el allo del desci ado si los e o es son demasiado
g andes y hay posibles a aques que pueden explo a es a ulne abilidad. Si el mensaje
se eu iliza en onces Sabe .PKE es ulne able a a aques que son adap i os. También hay
a aques que pueden ecupe a la cla e p i ada como pueden se los de iming,
elec omagné icos o simples allos.
Las únicas en ajas que p esen a SABER son la ue za de dos módulos que hacen que la
ans o mación de A2B (A o B) a B2A (B o A) sea más e icien e y que el ap endizaje con
edondeo no equie a gene ación de e o es.
T as habe supe ado nume osas p uebas, los expe os de NIST lo conside an un
algo i mo bas an e segu o lo que le ha pe mi ido llega a la inal de la e ce a onda del
concu so. Sin emba go, se quedó a las pue as de gana la onda que se la acabó lle ando
CRYSTALS-Kybe .
26
2) Enc yp , la cual pe mi e ejecu a la unción de ci ado del mensaje que es á en
o ma o bi .
3) Dec yp , que se enca ga de ejecu a la unción de desci ado del ex o ci ado y
de ol e el mensaje o iginal en o ma o bi .
El segundo a chi o es es .c que es a más au oma izado que el p ime a chi o. Pa a los
pa áme os n0, p, y w puedes ene dos opciones que son: in oduci los a mano o
de ini unos pa áme os po de ec o en el p opio código (así no hace al a es a
pensando en pa áme os pa a in oduci en cada ejecución). Pos e io men e la
ejecución exige que se in oduzca un mensaje, que se á el ex o pa a ci a y desci a .
Después de in oduci el mensaje se in oca una unción llamada “ ex _ o_bina y” que
se enca ga de aduci el mensaje, de o ma o ex o a o ma o bina io. Se p ocede a
inicializa los pa áme os n0, w, p y y ambién se inicializa la ma iz bina ia. A
con inuación, se llama a la unción “enc yp ” que se enca ga de ci a el mensaje que
es á en o ma o bina io, después se in oca la unción “dec yp ” que se enca ga de
desci a el ex o ci ado de ol iendo el mensaje o iginal en o ma o bina io y pa a
acaba se in oca la unción “bina y_ o_ ex ” que aduce el mensaje en o ma o bina io
a mensaje en o ma o ex o y es e se imp imi á po pan alla.
Después de habe compilado y ejecu ado la implemen ación a pa i de los dos a chi os,
se ecomienda u iliza el a chi o es .c po que es mucho más ápido, e icaz,
au oma izado y pe mi e juga con los pa áme os y el mensaje a in oduci .
3.4. Implemen ación seleccionada
Después de es udia dis in as implemen aciones del algo i mo de Classic McEliece, nos
decan amos po la implemen ación The-Classic-McEliece-mas e -c yp osys em. Es a
implemen ación pe mi e una mejo compilación ya que es a más au oma izada
pe mi iendo ejecu a cada pa e del p oceso po sepa ado, se ob ienen mejo es
esul ados en compa ación con las o as implemen aciones y la es uc u a del código
esul a más ácil de pa aleliza .
Hay dos mé odos pa a pode ejecu a el p oceso. El p ime o se ealiza median e la
compilación y ejecución del a chi o “ini .c”, que al ejecu a se pide al usua io que
in oduzca los pa áme os iniciales n0, p, w y pa a pode inicializa el p oceso
in ocando a la unción “mceliece_ini ” del iche o “mceliece.c”. Es a unción ealiza la
inicialización del sis ema de ci ado, ese ando p ime o espacio en memo ia y luego
in ocando a la unción “qc_mdpc_ini ” del iche o “qc_mdpc.c”. Es a unción se
enca ga ía de gene a la ma iz de código con los elemen os iniciales p opo cionados y
una semilla alea o ia o elegida po el usua io.
27
Después in oca la unción “gene a o _ma ix” del iche o “qc_mdpc.c”, pasándole la
ma iz de código ob enida po el mé odo “qc_mdpc_ini ” pa a pode c ea la ma iz
gene a iz G. Pa a pode c ea es a úl ima es necesa io que se hayan c eado
p e iamen e las ma ices H, H_in , H_0, Q, M e I. H es la ma iz de pa idad que se c ea
llamando a la unción “pa i y_check_ma ix”. Es e mé odo c ea dos ma ices H y M, usa
las unciones “make_ma ix” y “splice” pa a c ea las y luego las conca ena
ho izon almen e median e la unción “conca _ho izon al” c eando así la ma iz de
pa idad. H_in se ob iene a a és de la ma iz de pa idad, en es e caso como su nomb e
indica H_in es la ma iz in e ida de H c eada con el mé odo “ci c_ma ix_in e se”. H_0
y M son simplemen e unas ma ices nulas que se c ean con las unciones de
“make_ma ix” y “splice”. Q se ob iene a a és de la ma iz aspues a de la
mul iplicación de H_in y H_0 usando las unciones de “ anspose” y “ma ix_mul ”. M
se ans o ma haciendo la ma iz aspues a de la mul iplicación en e la e sión inicial
de M y H_in de la misma mane a cuando se c ea Q. Q iene ambién una e sión
mejo ada que se ob iene al hace la conca enación e ical en e la e sión inicial de Q
y la nue a e sión de M usando la unción “conca _ e ical”. I es la ma iz de iden idad
que se c ea con los mé odos de “ma _ini ” y “make_iden i y”. Pa a e mina , después
de gene a odas las ma ices an e io es, la ma iz gene a iz G se c ea a a és de la
conca enación ho izon al de I y Q. Es a ma iz G se gua da como cla e publica y así
inaliza el p oceso de inicialización del sis ema de ci ado. Pa a una mayo comp ensión
de lo que se ha desc i o éase la Figu a 5.
28
Figu a 5: Es uc u a del código
Después de inaliza con el p oceso de inicialización del sis ema de ci ado, se mos a á
un menú que pe mi e selecciona en e las siguien es opciones:
29
• QUIT: Al selecciona es a opción se ejecu a á un b eak pa a inaliza el p oceso.
i (op == 0)
{
b eak;
}
Código 1
• KEYGEN: Se c ea án las cla es pública y p i ada y se g aba án en unos iche os
x .
Pa a ob ene las cla es pública y p i ada se c ean dos ma ices: la ma iz H, que
se co esponde con la cla e p i ada y se c ea con el mé odo
“pa i y_check_ma ix” explicado p e iamen e en la inicialización del sis ema de
ci ado, y la ma iz G, que se co esponde con la cla e publica y que se c ea
median e el mé odo “gene a o ma ix” ambién mencionado an e io men e.
Pos e io men e se usa el mé odo “ge _ma ix_elemen ” pa a comp oba que los
angos de los elemen os son co ec os y al mismo iempo inse a los en el x
co espondien e y así comple a el p oceso de gene a los iche os x de las
cla es pública y p i ada. Pa a una mayo comp ensión ease la Figu a 6.
else i (op == 1)
{
bin_ma ix H = pa i y_check_ma ix(c yp ->code);
bin_ma ix G = gene a o _ma ix(c yp ->code);
FILE * p1, * p2;
p1 = open("P i a e_Key. x ", "a");
p in ( p1, "P i a e Key: Pa i y Check Ma ix: n");
o (in i = 0; i < H-> ows; i++)
{
o (in j = 0; j < H->cols; j++)
{
p in ( p1, "%hu ", ge _ma ix_elemen (H, i, j));
}
p in ( p1, " n n");
}
close( p1);
p2 = open("Public_Key. x ", "a");
p in ( p2, "Public Key: Gene a o Ma ix: n");
o (in i = 0; i < G-> ows; i++)
{
o (in j = 0; j < G->cols; j++)
{
p in ( p2, "%hu ", ge _ma ix_elemen (G, i, j));
30
}
p in ( p2, " n n");
}
close( p2);
p in ("Keys Gene a ed... n");
}
Código 2
31
Figu a 6: Es uc u a del código de la opción KEY GEN.
32
• ENCRYPT: Se ealiza el p oceso de ci ado de un mensaje in oducido po el
usua io y el esul ado se gua da á en un iche o x . El usua io p ime o in oduce
un mensaje de amaño K que pos e io men e se a a inse a en una ma iz
bina ia median e el mé odo “ma _ini ” pa a c ea la ma iz de amaño k y el
mé odo “se _ma ix_elemen ” pa a inse a el mensaje den o de la ma iz. A
con inuación, pa a pode inicializa el p oceso de sis ema de ci ado se in oca la
unción “mceliece_ini ” explicada en la c eación del “ini .c”.
Pos e io men e se c ea una ma iz M que llama al mé odo “enc yp ” al que se le
pasa el sis ema de ci ado c eado y el mensaje. El mé odo p ime o comp ueba si
la longi ud del mensaje es co ec a y después c ea una ma iz e o in ocando al
mé odo “ge _e o _ ec o ” que pe mi e c ea una ma iz con alo es alea o ios
de e o . Es o se hace p ime o c eando una ma iz con el mismo amaño del
mensaje usando la unción “ma _ini ” y luego se p ocede a c ea un alo
alea o io empleando la unción “ andom_ al”. Después se comp ueba si el
elemen o alea o io no es á en la ma iz usando “ge _ma ix_elemen ” y si ese
elemen o no es á en onces se inse a en la ma iz con el mé odo
“se _ma ix_elemen ”. Es e p oceso se epi e has a alcanza el amaño del
sis ema y comple a el p oceso de ci ado. Después se u ilizan los mé odos
“ma ix_mul” pa a ob ene la mul iplicación en e la ma iz que con iene la cla e
publica c eada p e iamen e y la ma iz que con iene el mensaje cuyo esul ado
se á usado po el mé odo “add_ma ix” pa a inco po a lo a la ma iz de e o .
El p oceso inaliza usando el mé odo “ge _ma ix_elemen ” pa a comp oba que
los angos de los elemen os es án co ec os y al mismo iempo inse a los en el
x co espondien e. Pa a una mayo comp ensión éase la Figu a 7.
else i (op == 2)
{
p in ("En e Message o leng h %d: n", k);
unsigned sho inp;
bin_ma ix msg = ma _ini (1, k);
o (in i = 0; i < k; i++)
{
scan ("%hu", &inp);
se _ma ix_elemen (msg, 0, i, inp);
}
mcc c yp = mceliece_ini (n0, p, w, );
bin_ma ix m = enc yp (msg, c yp );
FILE * p1;
p1 = open("Enc yp ion. x ", "a");
p in ( p1, "Enc yp ed message: n");
o (in i = 0; i < m->cols; i++)
{
33
p in ( p1, "%hu ", ge _ma ix_elemen (m, 0, i));
}
close( p1);
p in ("Enc yp ed... n");
}
Código 3
Figu a 7: Es uc u a del código de la opción ENCRYPT.
34
• DECRYPT: Se ealiza el p oceso de desci ado de un mensaje in oducido po el
usua io y el esul ado se gua da á en un iche o x . El usua io p ime o in oduce
un mensaje de amaño K que pos e io men e se a a inse a en una ma iz
bina ia median e el mé odo “ma _ini ” pa a c ea la ma iz de amaño k y el
mé odo “se _ma ix_elemen ” pa a inse a el mensaje den o de la ma iz. A
con inuación, pa a pode inicializa el p oceso de sis ema de ci ado se in oca la
unción “mceliece_ini ” explicada an e io men e.
Pos e io men e se c ea una ma iz M que llama al mé odo “dec yp ” al que se le
pasa el sis ema de ci ado c eado y el mensaje. El mé odo p ime o comp ueba si
la longi ud del mensaje es co ec a y después c ea una ma iz msg in ocando al
mé odo “decode” que se enca ga ía de decodi ica el mensaje ci ado. Pa a ello,
p ime o c ea la ma iz H (la ma iz de pa idad) u ilizando la unción
“pa i y_check_ma ix” del iche o “qc_mdpc.c”, empleando la ma iz de código.
Además, se usan los mé odos “splice” y “make_ma ix” del iche o “qc_mdpc.c”,
y “conca _ho izon al” del iche o “ma ix.c” pa a c ea una ma iz M y
pos e io men e conca ena la ho izon almen e con la ma iz H. A con inuación,
se c ea una ma iz syn, c eando pa a ello una ma iz aspues a con la unción
“ anspose” y luego mul iplicándola con la ma iz H usando el mé odo
“ma ix_mul”. Pos e io men e, en un doble bucle o se comp ueba qué
elemen os de las ma ices H y syn es án a 1 pa a ma ca los den o del ec o
unsi es ied empleando la unción “ge _ma ix_elemen ”. Luego se usa la unción
“ge _max” pa a ob ene el máximo elemen o del ec o unsi es ied que se á
u ilizado como lími e meno a la ho a de comp oba el es o de los elemen os
del ec o pa a pode eo dena la ma iz inicial usando “ge _ma ix_elemen ” y
“se _ma ix_elemen ”. Finalmen e, se usa el mé odo “add_ma ix” pa a añadi
la pa e di ida de la ma iz H po el mé odo “ma _splice” a la ma iz syn y así
conclui ía el p oceso de decodi icación del mensaje ci ado. Pa a e mina con el
p oceso del desci ado se llama a la unción “ma _splice” pa a di idi la ma iz
msg en un núme o de e minado de ilas y columnas. Después se usa el mé odo
“ge _ma ix_elemen ” pa a comp oba que los angos de los elemen os es án
co ec os y al mismo iempo inse a los en el x co espondien e. Pa a una
mayo comp ensión éase la Figu a 8.
else i (op == 3)
{
p in ("En e code o leng h %d: ", k);
unsigned sho inp;
bin_ma ix msg = ma _ini (1, k);
o (in i = 0; i < k; i++)
{
scan ("%hu", &inp);
se _ma ix_elemen (msg, 0, i, inp);
}
mcc c yp = mceliece_ini (n0, p, w, );
35
bin_ma ix m = dec yp (msg, c yp );
FILE * p1;
p1 = open("Dec yp ion. x ", "a");
p in ( p1, "Dec yp ed message: n");
o (in i = 0; i < m->cols; i++)
{
p in ( p1, "%hu ", ge _ma ix_elemen (m, 0, i));
}
close( p1);
p in ("Dec yp ed... n");
}
Código 4
42
#i nde _BINARYTEXT_H
#de ine _BINARYTEXT_H
oid bina y_ o_ ex (cha * inpu , cha * ou pu );
#endi
Código 6
#include "Bina yTex .h"
oid bina y_ o_ ex (cha * inpu , cha * ou pu ) {
in len = s len(inpu ), i, j;
unsigned cha c;
o (i = 0, j = 0; i < len; i += 8, j++) {
c = (inpu [i] - '0') * 128 + (inpu [i + 1] - '0') * 64 + (inpu [i
+ 2] - '0') * 32 +
(inpu [i + 3] - '0') * 16 + (inpu [i + 4] - '0') * 8 +
(inpu [i + 5] - '0') * 4 +
(inpu [i + 6] - '0') * 2 + (inpu [i + 7] - '0') * 1;
ou pu [j] = c;
}
ou pu [j] = ' 0';
}
Código 7
3.4.2. Tex Bina y.h y Tex Bina y.c
Es e a chi o con iene el código que se enca ga de aduci /con e i el mensaje en
o ma o ex o que se le pasa po pa áme o. Básicamen e ealiza una con e sión de
ca ac e es a núme os bina ios.
#include <s dio.h>
#include <s ing.h>
#i nde _TEXTBINARY_H
#de ine _TEXTBINARY_H
oid ex _ o_bina y(cha * inpu , cha * ou pu );
#endi
Código 8
#include "Tex Bina y.h"
#include <s dio.h>
#include <s ing.h>
oid ex _ o_bina y(cha * inpu , cha * ou pu ) {
in len = s len(inpu ), i, j;
43
o (i = 0, j = 0; i < len; i++, j += 8) {
unsigned cha c = inpu [i];
ou pu [j] = (c & 128) ? '1' : '0';
ou pu [j + 1] = (c & 64) ? '1' : '0';
ou pu [j + 2] = (c & 32) ? '1' : '0';
ou pu [j + 3] = (c & 16) ? '1' : '0';
ou pu [j + 4] = (c & 8) ? '1' : '0';
ou pu [j + 5] = (c & 4) ? '1' : '0';
ou pu [j + 6] = (c & 2) ? '1' : '0';
ou pu [j + 7] = (c & 1) ? '1' : '0';
}
ou pu [j] = ' 0';
}
Código 9
3.4.3. Dec yp .c
Es un a chi o que pe mi e in oduci los pa áme os n0, p, y w po consola. A
con inuación, p ocede a inicializa los llamando a la unción “mceliece_ini ”, luego in oca
la unción dec yp que se enca ga de desci a el ex o ci ado de ol iendo el mensaje
o iginal en o ma o bina io.
#include "qc_mdpc.h"
#include "ma ix.h"
#include "mceliece.h"
#include <s dlib.h>
#include <s dio.h>
in main(in a gc, cha cons *a g [])
{
in n0, p, w, ;
p in ("En e n0: ");
scan ("%d", &n0);
p in ("En e p: ");
scan ("%d", &p);
p in ("En e w: ");
scan ("%d", &w);
p in ("En e : ");
scan ("%d", & );
in k = (n0 - 1) * p;
p in ("En e code o leng h %d: ", k);
unsigned sho inp;
bin_ma ix msg = ma _ini (1, k);
o (in i = 0; i < k; i++)
{
scan ("%hu", &inp);
se _ma ix_elemen (msg, 0, i, inp);
44
}
mcc c yp = mceliece_ini (n0, p, w, );
bin_ma ix m = dec yp (msg, c yp );
FILE * p1;
p1 = open("Dec yp ion. x ", "a");
p in ( p1, "Dec yp ed message: n");
o (in i = 0; i < m->cols; i++)
{
p in ( p1, "%hu ", ge _ma ix_elemen (m, 0, i));
}
close( p1);
e u n 0;
}
Código 10
3.4.4. Enc yp .c
Es un a chi o que pe mi e in oduci los pa áme os n0, p, y w po consola. A
con inuación, p ocede a inicializa los llamando a la unción “mceliece_ini ”, luego in oca
la unción enc yp que se enca ga de ci a el mensaje que se le pasa en o ma o bina io
y p ocede a de ol e el ex o ci ado.
#include "qc_mdpc.h"
#include "ma ix.h"
#include "mceliece.h"
#include <s dlib.h>
#include <s dio.h>
in main(in a gc, cha cons *a g [])
{
in n0, p, w, ;
p in ("En e n0: ");
scan ("%d", &n0);
p in ("En e p: ");
scan ("%d", &p);
p in ("En e w: ");
scan ("%d", &w);
p in ("En e : ");
scan ("%d", & );
in k = (n0 - 1) * p;
p in ("En e Message o leng h %d: n", k);
unsigned sho inp;
bin_ma ix msg = ma _ini (1, k);
o (in i = 0; i < k; i++)
{
45
scan ("%hu", &inp);
se _ma ix_elemen (msg, 0, i, inp);
}
mcc c yp = mceliece_ini (n0, p, w, );
bin_ma ix m = enc yp (msg, c yp );
FILE * p1;
p1 = open("Enc yp ion. x ", "a");
p in ( p1, "Enc yp ed message: n");
o (in i = 0; i < m->cols; i++)
{
p in ( p1, "%hu ", ge _ma ix_elemen (m, 0, i));
}
close( p1);
e u n 0;
}
Código 11
3.4.5. key_gen.c
Es e a chi o se enca ga de c ea las cla es pública y p i ada. P ime o hay que in oduci
los pa áme os n0, w, y p, luego se gene an las ma ices H y G después de inicializa los
pa áme os in ocando la unción “qc_mdpc_ini ”. Después se c ean dos a chi os uno
que gua da á la cla e p i ada que se gene a usando la ma iz H y el o o a chi o
gua da á la cla e pública que se gene a u ilizando la ma iz G.
#include "qc_mdpc.h"
#include "ma ix.h"
#include <s dlib.h>
#include <s dio.h>
in main(in a gc, cha cons *a g [])
{
in n0, p, w, ;
p in ("En e n0: ");
scan ("%d", &n0);
p in ("En e p: ");
scan ("%d", &p);
p in ("En e w: ");
scan ("%d", &w);
p in ("En e : ");
scan ("%d", & );
mdpc code = qc_mdpc_ini (n0, p, w, );
bin_ma ix H = pa i y_check_ma ix(code);
bin_ma ix G = gene a o _ma ix(code);
46
FILE * p1, * p2;
p1 = open("P i a e_Key. x ", "a");
p in ( p1, "P i a e Key: Pa i y Check Ma ix: n");
o (in i = 0; i < H-> ows; i++)
{
o (in j = 0; j < H->cols; j++)
{
p in ( p1, "%hu ", ge _ma ix_elemen (H, i, j));
}
p in ( p1, " n n");
}
close( p1);
p2 = open("Public_Key. x ", "a");
p in ( p2, "Public Key: Gene a o Ma ix: n");
o (in i = 0; i < G-> ows; i++)
{
o (in j = 0; j < G->cols; j++)
{
p in ( p2, "%hu ", ge _ma ix_elemen (G, i, j));
}
p in ( p2, " n n");
}
close( p2);
e u n 0;
}
Código 12
3.4.6. ma ix.h y ma ix.c
Es e a chi o con iene la mayo pa e de unciones que se in ocan pa a inicializa
pa áme os, calcula ope aciones elacionadas con ma ices e inicializa las ma ices
bina ias. Las unciones que con iene es e a chi o son:
#include <s dbool.h>
#include "u ili y.h"
#i nde _MATRIX_H
#de ine _MATRIX_H
ypede s uc ma ix
{
in ows; //numbe o ows.
in cols; //numbe o columns.
unsigned sho *da a;
}*bin_ma ix;
47
bin_ma ix ma _ini (in ows, in cols);
unsigned sho ge _ma ix_elemen (bin_ma ix ma , in ow_idx, in
col_idx);
oid se _ma ix_elemen (bin_ma ix A, in ow_idx, in col_idx, unsigned
sho al);
oid se _ma ix_ ow(bin_ma ix A, in ow, unsigned sho * ec);
oid dele e_ma ix(bin_ma ix A);
bin_ma ix anspose(bin_ma ix A);
bin_ma ix ma _copy(bin_ma ix A);
bin_ma ix add_ ows(bin_ma ix A,in ow1, in ow2);
bin_ma ix add_ ows_new(bin_ma ix A,in ow1, in ow2, in i1, in i2);
bin_ma ix add_cols(bin_ma ix A,in col1, in col2, in a, in b);
bin_ma ix add_ma ix(bin_ma ix A, bin_ma ix B);
oid swap(bin_ma ix A, in ow1, in ow2);
bin_ma ix ma ix_ e (bin_ma ix A);
bin_ma ix ma ix_mul (bin_ma ix A, bin_ma ix B);
oid make_iden i y(bin_ma ix A);
bool is_iden i y(bin_ma ix A);
in is_ze o_ma ix(bin_ma ix A);
in ma _is_equal(bin_ma ix A, bin_ma ix B);
bin_ma ix ma ix_in e se(bin_ma ix A);
bin_ma ix ci c_ma ix_in e se(bin_ma ix A);
bin_ma ix ma _splice(bin_ma ix A, in ow1, in ow2, in col1, in
col2);
bin_ma ix ma _ke nel(bin_ma ix A);
bin_ma ix conca _ho izon al(bin_ma ix A, bin_ma ix B);
bin_ma ix conca _ e ical(bin_ma ix A, bin_ma ix B);
oid p in _ma ix(bin_ma ix A);
oid p in _ma ix_cha (bin_ma ix A, cha * ou pu );
#endi
Código 13
• Ma _ini : es a unción se enca ga de inicializa la ma iz bina ia ecibiendo como
pa áme os las ilas y columnas de la ma iz, y de uel e una ma iz bina ia.
bin_ma ix ma _ini (in ows, in cols)
{
i ( ows <= 0 || cols <= 0)
{
e u n NULL;
}
bin_ma ix A;
A = (bin_ma ix)sa e_malloc(sizeo (s uc ma ix));
A->cols = cols;
A-> ows = ows;
A->da a = (unsigned sho *)sa e_malloc( ows*cols*sizeo (unsigned
sho ));
e u n A;
48
}
Código 14
• Ge _ma ix_elemen : es a unción ecibe como pa áme os una ma iz bina ia,
un índice de ila y un índice de columna. Se enca ga de de ol e un elemen o de
la ma iz dado po las posiciones de la ila y columna pasadas p e iamen e po
pa áme os.
unsigned sho ge _ma ix_elemen (bin_ma ix ma , in ow_idx, in
col_idx)
{
i ( ow_idx < 0 || ow_idx >= ma -> ows || col_idx < 0 || col_idx >=
ma ->cols)
{
p in ("Ma ix index ou o ange n");
exi (0);
}
e u n ma ->da a[ ow_idx * (ma ->cols) + col_idx];
}
Código 15
• Se _ma ix_elemen : es a unción ecibe po pa áme os una ma iz bina ia, un
índice de posición de ila, un índice de posición de columna y un alo . Se enca ga
de inse a el alo pasado po pa áme o den o de la ma iz bina ia empleando
los índices de posición de la ila y la columna.
oid se _ma ix_elemen (bin_ma ix A, in ow_idx, in col_idx,
unsigned sho al)
{
i ( ow_idx < 0 || ow_idx >= A-> ows || col_idx < 0 || col_idx >= A-
>cols)
{
p in ("Ma ix index ou o ange n");
exi (0);
}
ma _elemen (A, ow_idx, col_idx) = al;
}
Código 16
• Se _ma ix_ ow: es a unción ecibe po pa áme os una ma iz bina ia, una ila
y un ec o . P ocede a inse a el ec o en la ila de la ma iz bina ia. El bucle se
puede pa aleliza pe ec amen e po que simplemen e se es án colocando los
elemen os en una ma iz A y es os elemen os se pueden ejecu a en hilos
independien es a la ez.
oid se _ma ix_ ow(bin_ma ix A, in ow, unsigned sho * ec)
{
i ( ow < 0 || ow >= A-> ows)
{
p in ("Row index ou o ange n");
49
exi (0);
}
o (in i = 0; i < A->cols; i++)
{
se _ma ix_elemen (A, ow, i, ec[i]);
}
}
Código 17
• Dele e_ma ix: es a unción ecibe po pa áme os una ma iz bina ia. P ocede
a bo a la ma iz bina ia y libe a el espacio en memo ia que ocupaba la ma iz.
oid dele e_ma ix(bin_ma ix A)
{
ee(A);
}
Código 18
• T anspose: es a unción ecibe po pa áme os una ma iz bina ia, p ocede a
de ol e la ma iz aspues a de la ma iz bina ia. Es a unción se puede
pa aleliza po que los elemen os de la ma iz A son independien es en e sí con
lo cual el doble bucle se puede colapsa en uno y ejecu a hilos independien es
al mismo iempo pa a ealiza la misma ope ación sob e odos los elemen os a
la ez. Pe o hay que ene cuidado po que el bucle in e no iene que se
secuencial espec o al p ime bucle pa a pode segui la cadena de ejecución de
los da os.
bin_ma ix anspose(bin_ma ix A)
{
bin_ma ix B;
B = ma _ini (A->cols, A-> ows);
o (in i = 0; i < A-> ows; i++)
{
o (in j = 0; j < A->cols; j++)
{
se _ma ix_elemen (B, j, i, ma _elemen (A, i, j));
}
}
e u n B;
}
Código 19
• Ma _copy: es a unción ecibe po pa áme os una ma iz bina ia. P ocede a
copia los da os de esa ma iz en o a ma iz bina ia que pos e io men e la
unción de uel e.
bin_ma ix ma _copy(bin_ma ix A)
50
{
bin_ma ix B;
in i;
B = ma _ini (A-> ows, A->cols);
memcpy(B->da a, A->da a, (A-> ows)*(A->cols)*(sizeo (unsigned
sho )));
e u n B;
}
Código 20
• Add_ ows: es a unción ecibe po pa áme os una ma iz bina ia y dos ilas. Se
enca ga de inse a una ila den o de o a ila de la ma iz bina ia y p ocede a
de ol e la al inaliza la ope ación. Pa a pa aleliza la unción hab ía que segui
el mismo concep o que en la unción “se _ma ix_ ow”.
bin_ma ix add_ ows(bin_ma ix A,in ow1, in ow2)
{
i ( ow1 < 0 || ow1 >= A-> ows || ow2 < 0 || ow2 >= A-> ows)
{
p in ("Ma ix index ou o ange n");
exi (0);
}
o (in i = 0; i < A->cols; i++)
{
ma _elemen (A, ow2, i) = (ma _elemen (A, ow1, i) ^
ma _elemen (A, ow2, i));
}
e u n A;
}
Código 21
• Add_ma ix: es a unción ecibe po pa áme os dos ma ices bina ias, p ocede
a inse a una de las ma ices den o de la o a y de uel e el esul ado. Hab ía
que segui el mismo esquema de pa alelización que en la unción “ anspose”.
bin_ma ix add_ma ix(bin_ma ix A, bin_ma ix B)
{
i (A-> ows != B-> ows || A->cols != B->cols)
{
p in ("Incompa ible dimenions o ma ix addi ion. n");
exi (0);
}
bin_ma ix emp = ma _ini (A-> ows, A->cols);
o (in i = 0; i < A-> ows; i++)
{
o (in j = 0; j < A->cols; j++)
51
{
se _ma ix_elemen ( emp, i, j, (ma _elemen (A, i, j) ^
ma _elemen (B, i, j)));
}
}
e u n emp;
}
Código 22
• Swap: es a unción ecibe po pa áme os una ma iz bina ia y dos ilas. Se
enca ga de in e cambia dos ilas de una ma iz y la de uel e. Pa a pode
pa aleliza es a unción hab ía que aplica el mismo mé odo u ilizado en la
unción “ anspose”.
oid swap(bin_ma ix A, in ow1, in ow2)
{
i ( ow1 < 0 || ow1 >= A-> ows || ow2 < 0 || ow2 >= A-> ows)
{
p in ("Ma ix index ou o ange n");
exi (0);
}
in emp;
o (in i = 0; i < A->cols; i++)
{
emp = ma _elemen (A, ow1, i);
ma _elemen (A, ow1, i) = ma _elemen (A, ow2, i);
ma _elemen (A, ow2, i) = emp;
}
}
Código 23
• Ma ix_ e : es a unción ecibe po pa áme os una ma iz bina ia. La unción
se enca ga de ob ene una e sión echlon educida de la ma iz bina ia y
de ol e ese esul ado. Pa a pa aleliza la unción hab ía que segui el mismo
concep o que en la unción “se _ma ix_ ow”.
bin_ma ix ma ix_ e (bin_ma ix A)
{
in lead = 0;
in ow_coun = A-> ows;
in col_coun = A->cols;
bin_ma ix emp = ma _ini ( ow_coun , col_coun );
emp = ma _copy(A);
in = 0;
bool e u n_ lag= alse;
o ( =0; < ow_coun ; ++)
{
i (ma _elemen ( emp, , ) == 0)
{
58
add_ ows(A, k, i);
i = i - 1;
b eak;
}
}
}
}
//p in ("Ou o o loop... n");
i (!is_iden i y(A))
{
p in ("Could no ind in e se, exi ing... n");
exi (-1);
}
e u n B;
}
Código 32
• Ma _splice: es a unción ecibe po pa áme os una ma iz bina ia, dos ilas y dos
columnas. Se enca ga de de ol e una ma iz bina ia que es á o mada po los
da os de la ma iz bina ia pasada po pa áme o limi ándola a un amaño
o mado po las ilas y columnas que ue on pasadas como pa áme os. Es a
unción se puede pa aleliza po que los elemen os de la ma iz A son
independien es en e sí con lo cual el doble bucle se puede colapsa en uno y
ejecu a simul áneamen e dis in os hilos pa a ealiza la misma ope ación sob e
odos los elemen os a la ez. Pe o hay que ene cuidado po que el bucle in e no
iene que se secuencial espec o al p ime bucle pa a pode segui la cadena de
ejecución de los da os.
bin_ma ix ma _splice(bin_ma ix A, in ow1, in ow2, in col1, in
col2)
{
in ow_coun = ow2 - ow1 + 1;
in col_coun = col2 - col1 + 1;
in idx1, idx2;
bin_ma ix = ma _ini ( ow_coun , col_coun );
o (in i = 0; i < ow_coun ; i++)
{
idx1 = ow1 + i;
o (in j = 0; j < col_coun ; j++)
{
idx2 = col1 + j;
se _ma ix_elemen ( , i, j, ma _elemen (A, idx1, idx2));
}
}
e u n ;
59
}
Código 33
• Ma _ke nel: es a unción ecibe po pa áme os una ma iz bina ia y se enca ga
de de ol e una ma iz donde se encon ó su base del espacio del ke nel. Es a
unción se puede pa aleliza po que no hay dependencias en e los elemen os
de la ma iz A con lo cual el doble bucle se puede colapsa en uno y ejecu a al
mismo iempo a ios hilos independien es pa a ealiza la misma ope ación
sob e odos los elemen os a la ez. Pe o hay que ene cuidado po que el bucle
in e no iene que se secuencial espec o el p ime bucle pa a pode segui la
cadena de ejecución de los da os. El segundo bucle se puede pa aleliza
pe ec amen e po que simplemen e se es án colocando los elemen os en una
ma iz emp y es os elemen os se pueden ejecu a a la ez en hilos
independien es. La úl ima pa e de la unción segui ía la misma secuencia que el
p ime bucle.
bin_ma ix ma _ke nel(bin_ma ix A)
{
in ow_coun = A-> ows;
in col_coun = A->cols;
bin_ma ix emp = ma _ini (col_coun , ow_coun + col_coun );
bin_ma ix ans = ma _ini (col_coun , col_coun - ow_coun );
o (in i = 0; i < emp-> ows; i++)
{
o (in j = 0; j < ow_coun ; j++)
{
se _ma ix_elemen ( emp, i, j, ma _elemen (A, j, i));
}
}
o (in i = 0; i < col_coun ; i++)
{
se _ma ix_elemen ( emp, i, i + ow_coun , 1);
}
in = 0;
bool e u n_ lag = alse;
o (in = 0; < ow_coun ; ++)
{
i (ma _elemen ( emp, , ) == 0)
{
in i;
60
o (i = + 1; i < emp-> ows; i++)
{
i (ma _elemen ( emp, i, ) && e u n_ lag== alse)
{
swap( emp, , i);
e u n_ lag= ue;
}
}
i (i == emp-> ows)
{
ans = ma _splice( emp, ow_coun , col_coun - 1, ow_coun ,
ow_coun + col_coun - 1);
e u n (ma ix_ e (ans));
}
}
else
{
o (in i = 0; i < emp-> ows; i++)
{
i (ma _elemen ( emp, i, ) && i != )
{
add_ ows( emp, , i);
}
}
}
}
ans = ma _splice( emp, ow_coun , col_coun - 1, ow_coun ,
ow_coun + col_coun - 1);
e u n (ma ix_ e (ans));
}
Código 34
• Conca _ho izon al: es a unción ecibe po pa áme os dos ma ices bina ias. Se
enca ga de de ol e la ma iz ob enida al ealiza la conca enación ho izon al de
las ma ices pasadas como pa áme os. Pa a pa aleliza es a unción hab ía que
aplica el mismo mé odo que a la unción “ anspose”.
bin_ma ix conca _ho izon al(bin_ma ix A, bin_ma ix B)
{
i (A-> ows != B-> ows)
{
p in ("Incompa ible dimensions o he wo ma ices. Numbe o
ows should be same. n");
exi (0);
}
bin_ma ix emp = ma _ini (A-> ows, A->cols + B->cols);
o (in i = 0; i < emp-> ows; i++)
61
{
o (in j = 0; j < emp->cols; j++)
{
i (j < A->cols)
{
se _ma ix_elemen ( emp, i, j, ma _elemen (A, i, j));
}
else
{
se _ma ix_elemen ( emp, i, j, ma _elemen (B, i, j - A-
>cols));
}
}
}
e u n emp;
}
Código 35
• Conca _ e ical: es a unción ecibe po pa áme os dos ma ices bina ias. Se
enca ga de de ol e la ma iz ob enida al ealiza la conca enación e ical de las
ma ices pasadas como pa áme os. Pa a pa aleliza es a unción hab ía que
aplica el mismo mé odo que a la unción “ anspose”.
bin_ma ix conca _ e ical(bin_ma ix A, bin_ma ix B)
{
i (A->cols != B->cols)
{
p in ("Incompa ible dimensions o he wo ma ices. Numbe o
ows should be same. n");
exi (0);
}
bin_ma ix emp = ma _ini (A-> ows + B-> ows, A->cols);
o (in i = 0; i < emp-> ows; i++)
{
o (in j = 0; j < emp->cols; j++)
{
i (i < A-> ows)
{
se _ma ix_elemen ( emp, i, j, ma _elemen (A, i, j));
}
else
{
se _ma ix_elemen ( emp, i, j, ma _elemen (B, i - A-> ows,
j));
}
62
}
}
e u n emp;
}
Código 36
• P in _ma ix: es a unción ecibe po pa áme os una ma iz bina ia y p ocede a
imp imi esa ma iz po pan alla en o ma o bina io. Pa a pa aleliza es a unción
hab ía que aplica el mismo mé odo que a la unción “ anspose”.
oid p in _ma ix(bin_ma ix A)
{
o (in i = 0; i < A-> ows; i++)
{
o (in j = 0; j < A->cols; j++)
{
p in ("%hu ", ma _elemen (A, i, j));
}
p in (" n");
}
}
Código 37
• P in _ma ix_cha : es a unción ecibe po pa áme os una ma iz bina ia y un
ou pu y p ocede a imp imi esa ma iz po pan alla en o ma o ex o. Pa a
pa aleliza es a unción hab ía que aplica el mismo mé odo que a la unción
“ anspose”.
oid p in _ma ix_cha (bin_ma ix A, cha * ou pu )
{
o (in i = 0; i < A-> ows; i++)
{
o (in j = 0; j < A->cols; j++)
{
cha num[2];
sp in (num,"%hu",ma _elemen (A, i, j));
s ca (ou pu ,num);
}
p in (" n");
}
}
Código 38
3.4.7. mceliece.h y mceliece.c
63
Es e a chi o con iene unciones que se in ocan y u ilizan pa a inicializa pa áme os y
gene a ec o es. Las unciones que con iene el a chi o son las siguien es:
#include "qc_mdpc.h"
#include "ma ix.h"
#include "u ili y.h"
#i nde MCELIECE_H
#de ine MCELIECE_H
ypede s uc mceliece
{
mdpc code;
bin_ma ix public_key;
}*mcc;
mcc mceliece_ini (in n0, in p, in w, in );
oid dele e_mceliece(mcc A);
bin_ma ix ge _e o _ ec o (in len, in );
bin_ma ix enc yp (bin_ma ix msg, mcc c yp );
bin_ma ix dec yp (bin_ma ix wo d, mcc c yp );
#endi
Código 39
• Mceliece_ini : es a unción ecibe como pa áme os los da os n0, p, y w y
p ocede a c ea el c ip osis ema de mceliece u ilizando los pa áme os dados.
mcc mceliece_ini (in n0, in p, in w, in )
{
mcc c yp ;
c yp = (mcc)sa e_malloc(sizeo (s uc mceliece));
c yp ->code = qc_mdpc_ini (n0, p, w, );
c yp ->public_key = gene a o _ma ix(c yp ->code);
e u n c yp ;
}
Código 40
• Dele e_mceliece: es a unción ecibe como pa áme o un c ip osis ema, y
p ocede a bo a lo y libe a el espacio en memo ia que ue ocupado po él.
oid dele e_mceliece(mcc A)
{
dele e_qc_mdpc(A->code);
dele e_ma ix(A->public_key);
ee(A);
}
Código 41
64
• Ge _e o _ ec o : es a unción ecibe como pa áme os una longi ud y un peso.
Se enca ga de gene a un ec o de e o alea o io u ilizando los pa áme os
dados .
bin_ma ix ge _e o _ ec o (in len, in )
{
bin_ma ix e o = ma _ini (1, len);
in weigh = 0;
in idx;
while(weigh < )
{
idx = andom_ al(1, len - 1, -1);
i (!ge _ma ix_elemen (e o , 0, idx))
{
se _ma ix_elemen (e o , 0, idx, 1);
weigh ++;
}
}
e u n e o ;
}
Código 42
• Enc yp : es a unción ecibe como pa áme os una ma iz bina ia y un
c ip osis ema. Se enca ga de ci a la ma iz bina ia que con iene el mensaje,
pa a ello in oca a las unciones de add_ma ix y ge _e o _ ec o y usa el
c ip osis ema pa a de ol e el ex o ci ado.
bin_ma ix enc yp (bin_ma ix msg, mcc c yp )
{
i (msg->cols != c yp ->public_key-> ows)
{
p in ("Leng h o message is inco ec . n");
exi (0);
}
bin_ma ix e o = ge _e o _ ec o (c yp ->code->n, c yp ->code-
> );
bin_ma ix wo d = add_ma ix(ma ix_mul (msg, c yp ->public_key),
e o );
e u n wo d;
}
Código 43
• Dec yp : es a unción ecibe como pa áme os una ma iz bina ia y un
c ip osis ema. Se enca ga de desci a el ex o ci ado que iene dado en la
ma iz bina ia, llamando pa a ello a las unciones decode y ma _splice, que
emplean el c ip osis ema pa a de ol e el mensaje o iginal en o ma o bina io.
bin_ma ix dec yp (bin_ma ix wo d, mcc c yp )
65
{
i (wo d->cols != c yp ->code->n)
{
p in ("Leng h o message is inco ec . n");
exi (0);
}
bin_ma ix msg = decode(wo d, c yp ->code);
msg = ma _splice(msg, 0, msg-> ows - 1, 0, c yp ->code->k - 1);
e u n msg;
}
Código 44
3.4.8. qc_mdpc.h y qc_mdpc.c
Es e a chi o con iene una se ie de unciones que se enca gan de ealiza nume osas
ope aciones. Es as unciones son:
#include "ma ix.h"
#include "u ili y.h"
#i nde QC_MDPC_H
#de ine QC_MDPC_H
ypede s uc qc_mdpc
{
unsigned sho * ow;
in n0, p, w, , n, k, ;
}*mdpc;
mdpc qc_mdpc_ini (in n0, in p, in w, in );
oid dele e_qc_mdpc(mdpc A);
in andom_ al(in min, in max, unsigned seed);
in ge _ ow_weigh (unsigned sho * ow, in min, in max);
oid ese _ ow(unsigned sho * ow, in min, in max);
unsigned sho * shi (unsigned sho * ow, in x, in len);
unsigned sho * splice(unsigned sho * ow, in min, in max);
bin_ma ix make_ma ix(in ows, in cols, unsigned sho * ec, in x);
bin_ma ix gene a o _ma ix(mdpc code);
bin_ma ix pa i y_check_ma ix(mdpc code);
in ge _max(in * ec, in len);
bin_ma ix encode(bin_ma ix ec, mdpc code);
bin_ma ix decode(bin_ma ix wo d, mdpc code);
#endi
Código 45
• Qc_mdpc_ini : es a unción ecibe como pa áme os los da os n0, p, y w y
p ocede a c ea un código de comp obación de pa idad de densidad mode ada
(MDPC)u ilizando los pa áme os dados.
66
mdpc qc_mdpc_ini (in n0, in p, in w, in )
{
mdpc code;
code = (mdpc)sa e_malloc(sizeo (s uc qc_mdpc));
code->n0 = n0;
code->p = p;
code->w = w;
code-> = ;
code->n = n0 * p;
code-> = p;
code->k = (n0 - 1) * p;
unsigned seed;
code-> ow = (unsigned sho *)calloc(n0 * p, sizeo (unsigned
sho ));
p in ("Inpu seed o -1 o use de aul seed: ");
scan ("%u", &seed);
ime_ x;
i (seed == -1)
{
s and((unsigned) ime(& x));
}
else
{
s and(seed);
}
while(1)
{
in lag = 0;
in idx;
while( lag < w)
{
idx = andom_ al(0, (n0 * p) - 1, seed);
i (!code-> ow[idx])
{
code-> ow[idx] = 1;
lag = lag + 1;
}
}
i ((ge _ ow_weigh (code-> ow, (n0 - 1) * p, (n0 * p)-1)) % 2
== 1)
{
b eak;
}
ese _ ow(code-> ow, 0, n0 * p);
}
p in ("MDPC code gene a ed.... n");
e u n code;
}
67
Código 46
• Dele e_qc_mdpc: es a unción ecibe como pa áme o un código MDPC y
p ocede a bo a lo y libe a el espacio en memo ia que ue ocupado po es e
código.
oid dele e_qc_mdpc(mdpc A)
{
ee(A);
}
Código 47
• Random_ al: es a unción ecibe como pa áme os un alo mínimo, un alo
máximo y una semilla. Se enca ga de de ol e un núme o en e o alea o io
c eado den o del ango limi ado po es os alo es máximo y mínimo.
in andom_ al(in min, in max, unsigned seed)
{
in ;
cons unsigned in ange = 1 + max - min;
cons unsigned in bucke s = RAND_MAX / ange;
cons unsigned in limi = bucke s * ange;
do
{
= and();
} while ( >= limi );
e u n min + ( / bucke s);
}
Código 48
• Ge _ ow_weigh : es a unción ecibe como pa áme os un mínimo, un máximo
y una ila. P ocede a de ol e el peso de la ila en el ango o mado po el máximo
y el mínimo. Exis e la opción de pa alelización po que al se independien es los
elemen os del ec o ow es os se pueden comp oba si son iguales a 1 de golpe
ejecu ándolos en hilos sepa ados en ez de espe a a que inalice cada uel a del
bucle pa a inicia la siguien e comp obación y es o pe mi i á mejo a el
endimien o de la unción.
in ge _ ow_weigh (unsigned sho * ow, in min, in max)
{
in weigh = 0;
in i;
o (i = min; i < max + 1; i++)
{
i ( ow[i] == 1)
{
weigh ++;
}
74
4.Implemen ación ealizada
En es e capí ulo abo da emos las di e en es mejo as sob e el código, ealizadas en dos
“ ondas”. Ambas secciones incluyen aquellas unciones mejo adas, el po qué de su
mejo a, además de su código co espondien e. Pa a acili a la lec u a y comp esión de
es e capí ulo epe i emos in o mación que ya sea ha p esen ado en el capí ulo 3.
4.1. P ime a onda de mejo as
La implemen ación del algo i mo Classic McEliece que ue elegida pe mi e la opción de
una mejo a de endimien o a la ho a de ejecu a el p oceso comple o de ci ado y
desci ado median e el uso del lenguaje de p og amación OpenACC. Con es e lenguaje
se puede ealiza una pa alelización del código o iginal que pe mi a compila y ejecu a
las pa es del código modi icadas y mejo adas en un emulado GPU y pode así ope a
con las ma ices indicadas en pa alelo. Es e p oceso se conoce como pa alelización y se
enca ga de di idi una a ea o un p og ama en pa es más pequeñas y ejecu a las de
mane a simul ánea en múl iples hilos de ejecución o p ocesado es, con el obje i o de
mejo a el endimien o y ap o echa al máximo los ecu sos disponibles en sis emas
mul ip ocesado o mul i-hilo. Hay que ene en cuen a que pa a pode emplea la
pa alelización los da os ienen que se independien es ya que si exis e algún ipo de
dependencia hab ía que espe a a que un da o se e mine de ejecu a pa a pode lanza
el siguien e. El ejemplo más sencillo es un doble bucle o , básicamen e el doble bucle
se colapsa en uno único o mando un bus en el que se ejecu an las ope aciones sob e
odos los elemen os de ese bus al mismo iempo g acias al uso de hilos que se c ean
den o del bus, pe mi iendo pone un elemen o de la ma iz den o de un hilo y
ejecu a lo de o ma independien e del es o de hilos que se ejecu an al mismo iempo.
Una ez que inaliza la ejecución el espacio de memo ia ese ado pa a los hilos se
libe a. Es e mé odo es muy e icaz a la ho a de mejo a el endimien o si se quie en ci a
y desci a mensajes de g an can idad de ca ac e es.
//Inicialización del a ay
o (i= 0; i < SIZE; i++){
o (j = 0; j < SIZE; j++){
a ay[i][j] = i + j;
}
}
//Pa alelización del bucle o con OpenACC
#p agma acc pa allel loop
o (i= 0; i < SIZE; i++){
o (j = 0; j < SIZE; j++){
a ay[i][j] *= 2;
}
}
Código 60
75
A con inuación, se mues an y desc iben las mejo as ealizadas sob e el código
explicando qué acción ealiza cada mé odo y cuáles son los cambios que se han ealizado
sob e el código usando el lenguaje de p og amación OpenACC.
4.1.1. ma ix.c
• Se _ma ix_ ow: es a unción ecibe po pa áme os una ma iz bina ia, un
índice de posición de ila, un índice de posición de columna y un ec o de alo es
de la ma iz auxilia . Se enca ga de inse a el alo pasado po pa áme o den o
de la ma iz bina ia empleando los índices de posición de la ila y de la columna.
Se pa aleliza el bucle de la unción po que al se los elemen os de la ma iz
independien es se pueden di idi en múl iples hilos de ejecución y cada uno
puede abaja en secciones di e en es del bucle.
oid se _ma ix_ ow(bin_ma ix A, in ow, unsigned sho * ec)
{
i ( ow < 0 || ow >= A-> ows)
{
p in ("Row index ou o ange n");
exi (0);
}
#p agma acc pa allel loop independen
o (in i = 0; i < A->cols; i++)
{
se _ma ix_elemen (A, ow, i, ec[i]);
}}
Código 61
• T anspose: es a unción ecibe po pa áme o una ma iz bina ia y de uel e la
ma iz aspues a de la ma iz bina ia. El bucle ex e io se ejecu a en pa alelo y
puede se di idido en múl iples hilos de ejecución. Po o o lado, el bucle in e no
se ejecu a en se ie lo que ga an iza que cada hilo de ejecución acceda a los
elemen os de la ma iz de mane a secuencial y sin con lic os.
bin_ma ix anspose(bin_ma ix A)
{
bin_ma ix B;
B = ma _ini (A->cols, A-> ows);
#p agma acc pa allel loop independen
o (in i = 0; i < A-> ows; i++)
{
#p agma acc loop seq
o (in j = 0; j < A->cols; j++)
{
se _ma ix_elemen (B, j, i, ma _elemen (A, i, j));
}
}
76
e u n B;
}
Código 62
• Add_ ows: es a unción ecibe po pa áme os una ma iz bina ia y dos ilas. Se
enca ga de inse a una ila den o de o a ila de la ma iz bina ia y p ocede a
de ol e la al inaliza la ope ación. El bucle se ejecu a en pa alelo y puede se
di idido en múl iples hilos de ejecución. Cada hilo de ejecución se enca ga de
ac ualiza un subconjun o de los elemen os de la ila ow2.
bin_ma ix add_ ows(bin_ma ix A,in ow1, in ow2)
{
i ( ow1 < 0 || ow1 >= A-> ows || ow2 < 0 || ow2 >= A-> ows)
{
p in ("Ma ix index ou o ange n");
exi (0);
}
#p agma acc pa allel loop independen
o (in i = 0; i < A->cols; i++)
{
ma _elemen (A, ow2, i) = (ma _elemen (A, ow1, i) ^
ma _elemen (A, ow2, i));
}
e u n A;
}
Código 63
• Add_ma ix: es a unción ecibe po pa áme os dos ma ices bina ias, p ocede
a inse a una de las ma ices den o de la o a y de uel e el esul ado. El bucle
ex e io se ejecu a en pa alelo y puede se di idido en múl iples hilos de
ejecución. Po o o lado, el bucle in e no se ejecu a en se ie lo que ga an iza que
cada hilo de ejecución acceda a los elemen os de la ma iz de mane a secuencial
y sin con lic os.
bin_ma ix add_ma ix(bin_ma ix A, bin_ma ix B)
{
i (A-> ows != B-> ows || A->cols != B->cols)
{
p in ("Incompa ible dimenions o ma ix addi ion. n");
exi (0);
}
bin_ma ix emp = ma _ini (A-> ows, A->cols);
#p agma acc pa allel loop independen
o (in i = 0; i < A-> ows; i++)
{
#p agma acc loop seq
o (in j = 0; j < A->cols; j++)
{
77
se _ma ix_elemen ( emp, i, j, (ma _elemen (A, i, j) ^
ma _elemen (B, i, j)));
}
}
e u n emp;
}
Código 64
• Swap: es a unción ecibe po pa áme os una ma iz bina ia y dos ilas. Se
enca ga de in e cambia dos ilas de una ma iz. El bucle se ejecu a en pa alelo
y puede se di idido en múl iples hilos de ejecución. Cada hilo de ejecución se
enca ga de in e cambia un subconjun o de los elemen os de las dos ilas, lo que
pe mi e una ejecución más ápida en sis emas pa alelos.
oid swap(bin_ma ix A, in ow1, in ow2)
{
i ( ow1 < 0 || ow1 >= A-> ows || ow2 < 0 || ow2 >= A-> ows)
{
p in ("Ma ix index ou o ange n");
exi (0);
}
in emp;
#p agma acc pa alleel loop independen
o (in i = 0; i < A->cols; i++)
{
emp = ma _elemen (A, ow1, i);
ma _elemen (A, ow1, i) = ma _elemen (A, ow2, i);
ma _elemen (A, ow2, i) = emp;
}}
Código 65
• Ma ix_ e : es a unción ecibe po pa áme o una ma iz bina ia. La unción se
enca ga de ob ene una e sión echlon educida de la ma iz bina ia y de ol e
ese esul ado. Cada uno de los bucles de la unción con iene un p agma pa a
pode ejecu a los en pa alelo, así puede se di idido en múl iples hilos de
ejecución.
bin_ma ix ma ix_ e (bin_ma ix A)
{
in lead = 0;
in ow_coun = A-> ows;
in col_coun = A->cols;
bin_ma ix emp = ma _ini ( ow_coun , col_coun );
emp = ma _copy(A);
in = 0;
while( < ow_coun )
{
i (ma _elemen ( emp, , ) == 0)
78
{
in i;
#p agma acc pa allel loop independen
o (i = + 1; i < emp-> ows; i++)
{
i (ma _elemen ( emp, i, ) == 1)
{
swap( emp, , i);
b eak;
}
}
i (i == ow_coun )
{
p in ("Ma ix canno be ans o med in o ow echlon o m...");
exi (1);
}
}
else
{
#p agma acc pa allel loop independen
o (in i = 0; i < ow_coun ; i++)
{
i (ma _elemen ( emp, i, ) == 1 && i != )
{
add_ ows( emp, , i);
}
}
++;
}
}
e u n emp;
}
Código 66
• Ma ix_mul : es a unción ecibe po pa áme os dos ma ices bina ias. Se
enca ga de mul iplica las dos ma ices que ue on pasadas po pa áme o y
de uel e el esul ado. El código es á u ilizando la di ec i a #p agma acc pa a
pa aleliza los bucles ex e nos e in e nos, indicando que se pueden ejecu a en
pa alelo independien emen e. Además, u iliza la di ec i a loop seq pa a indica
que el bucle más in e no no puede ejecu a se en pa alelo debido a la
dependencia de da os.
bin_ma ix ma ix_mul (bin_ma ix A, bin_ma ix B)
{
i (A->cols != B-> ows)
{
p in ("Ma ices a e incompa ible, check dimensions... n");
exi (0);
}
79
bin_ma ix C;
C = ma _ini (A-> ows, B->cols);
bin_ma ix B_ emp = anspose(B);
#p agma acc pa alleel loop independen
o (in i = 0; i < A-> ows; i++)
{
#p agma acc pa alleel loop independen
o (in j = 0 ; j < B->cols; j++)
{
unsigned sho al = 0;
#p agma acc loop seq
o (in k = 0; k < B-> ows; k++)
{
al = ( al ^ (ma _elemen (A, i, k) & ma _elemen (B_ emp, j,
k)));
}
ma _elemen (C, i, j) = al;
}
}
e u n C;
}
Código 67
• Make_iden i y: es a unción ecibe po pa áme os una ma iz bina ia y p ocede
a es ablece la como una ma iz de iden idad. El código es á u ilizando la di ec i a
#p agma acc pa a pa aleliza el bucle ex e no, indicando que se puede ejecu a
en pa alelo independien emen e. Además, u iliza la di ec i a loop seq pa a
indica que el bucle in e no no puede ejecu a se en pa alelo debido a la
dependencia de da os.
oid make_inden i y(bin_ma ix A)
{
#p agma acc pa allel loop independen
o (in i = 0; i < A-> ows; i++)
{
#p agma acc loop seq
o (in j = 0; j < A->cols; j++)
{
i (i == j)
{
ma _elemen (A, i, j) = 1;
}
else
{
ma _elemen (A, i, j) = 0;
}
80
}
}
}
Código 68
• Is_iden i y: es a unción ecibe po pa áme o una ma iz bina ia y p ocede a
comp oba si es una ma iz de iden idad de ol iendo una señal pa a indica si es
e dade o o also. El código es á u ilizando la di ec i a #p agma acc pa a
pa aleliza el bucle ex e no, indicando que se puede ejecu a en pa alelo
independien emen e. Además, u iliza la di ec i a loop seq pa a indica que el
bucle in e no no puede ejecu a se en pa alelo debido a la dependencia de da os.
bool is_iden i y(bin_ma ix A)
{
bool lag = ue;
#p agma acc pa allel loop independen
o (in i = 0; i < A-> ows; i++)
{
#p agma acc loop seq
o (in j = 0; j < A->cols; j++)
{
i (i == j)
{
i (ma _elemen (A, i, j) == 0)
{
lag = alse;
e u n lag;
}
}
else
{
i (ma _elemen (A, i, j) == 1)
{
lag = alse;
e u n lag;
}
}
}
}
e u n lag;
}
Código 69
• Is_ze o_ma ix: es a unción ecibe po pa áme o una ma iz bina ia y p ocede
a comp oba si es una ma iz de ce os de ol iendo una señal pa a indica si es
e dade o o also. El código es á u ilizando la di ec i a #p agma acc pa a
pa aleliza el bucle ex e no, indicando que se puede ejecu a en pa alelo
independien emen e. Además, u iliza la di ec i a loop seq pa a indica que el
bucle in e no no puede ejecu a se en pa alelo debido a la dependencia de da os.
81
in is_ze o_ma ix(bin_ma ix A)
{
in lag = 1;
#p agma acc pa allel loop independen
o (in i = 0; i < A-> ows; i++)
{
#p agma acc loop seq
o (in j = 0; j < A->cols; j++)
{
i (ma _elemen (A, i, j) != 0)
{
lag = 0;
e u n lag;
}
}
}
e u n lag;
}
Código 70
• Ma _is_equal: es a unción ecibe po pa áme os dos ma ices bina ias y
p ocede a comp oba si esas ma ices son iguales de ol iendo una señal pa a
indica si es e dade o o also. El código es á u ilizando la di ec i a #p agma acc
pa a pa aleliza el bucle ex e no, indicando que se puede ejecu a en pa alelo
independien emen e. Además, u iliza la di ec i a loop seq pa a indica que el
bucle in e no no puede ejecu a se en pa alelo debido a la dependencia de da os.
in ma _is_equal(bin_ma ix A, bin_ma ix B)
{
in lag = 1;
i (A-> ows != B-> ows || A->cols != B->cols)
{
lag = 0;
e u n lag;
}
#p agma acc pa allel loop independen
o (in i = 0; i < A-> ows; i++)
{
#p agma acc loop seq
o (in j = 0; j < A->cols; j++)
{
i (ma _elemen (A, i, j) != ma _elemen (B, i, j))
{
lag = 0;
e u n lag;
}
}
}
82
e u n lag;
}
Código 71
• Add_ ows_new: es a unción ecibe po pa áme os una ma iz bina ia, dos ilas
y un ango. Se enca ga de inse a los elemen os de la p ime a ila a la segunda
ila en el lími e del ango y p ocede a de ol e la ma iz. El bucle de la unción se
puede ejecu a en pa alelo pe mi iendo di idi lo en múl iplos hilos pa a ealiza
la ejecución.
bin_ma ix add_ ows_new(bin_ma ix A,in ow1, in ow2, in a, in b)
{
i ( ow1 < 0 || ow1 >= A-> ows || ow2 < 0 || ow2 >= A->cols)
{
p in ("Ma ix index ou o ange n");
exi (0);
}
#p agma acc pa allel loop independen
o (in i = a; i < b; i++)
{
ma _elemen (A, ow2, i) = (ma _elemen (A, ow1, i) ^
ma _elemen (A, ow2, i));
}
e u n A;
}
Código 72
• Add_cols: es a unción ecibe po pa áme os una ma iz bina ia, dos columnas
y un ango. Se enca ga de inse a los elemen os de la p ime a ila a la segunda
ila en el lími e del ango y p ocede a de ol e la ma iz. El bucle de la unción se
puede ejecu a en pa alelo pe mi iendo di idi lo en múl iples hilos pa a ealiza
la ejecución.
bin_ma ix add_cols(bin_ma ix A,in col1, in col2, in a, in b)
{
i (col1 < 0 || col1 >= A->cols || col2 < 0 || col2 >= A->cols)
{
p in ("Ma ix index ou o ange n");
exi (0);
}
#p agma acc pa allel loop independen
o (in i = a; i < b; i++)
{
ma _elemen (A, i, col2) = (ma _elemen (A, i, col1) ^
ma _elemen (A, i, col2));
}
e u n A;
}
Código 73
83
• Ci c_ma ix_in e se: es a unción ecibe po pa áme os una ma iz bina ia, y
p ocede a de ol e la ma iz in e sa de la ma iz dada. El código es á u ilizando
la di ec i a #p agma acc pa a pa aleliza el bucle ex e no, indicando que se
puede ejecu a en pa alelo independien emen e. Además, u iliza la di ec i a
loop seq pa a indica que el bucle in e no no puede ejecu a se en pa alelo
debido a la dependencia de da os.
bin_ma ix ci c_ma ix_in e se(bin_ma ix A)
{
i (A-> ows != A->cols)
{
p in ("In e se no possible... n");
exi (0);
}
i (is_iden i y(A))
{
e u n A;
}
bin_ma ix B;
B = ma _ini (A-> ows, A->cols);
make_inden i y(B);
in i;
in lag, p e _ lag = 0;
#p agma acc pa allel loop independen
o (i = 0; i < A->cols; i++)
{
i (ma _elemen (A, i, i) == 1)
{
#p agma acc loop seq
o (in j = 0; j < A-> ows; j++)
{
i (i != j && ma _elemen (A, j, i) == 1)
{
add_ ows_new(B, i, j, 0, A->cols);
add_ ows_new(A, i, j, i, A->cols);
}
}
}
else
{
in k;
#p agma acc loop seq
o (k = i + 1; k < A-> ows; k++)
{
90
}
Código 82
• Shi : es a unción ecibe como pa áme os una longi ud, núme o de posiciones
y una ila. P ocede a de ol e una ila donde un núme o de posiciones han sido
o adas a la de echa. Se pa aleliza el bucle de la unción po que al se los
elemen os de la ma iz independien es, se pueden di idi en múl iples hilos de
ejecución y cada uno puede abaja en secciones di e en es del bucle.
unsigned sho * shi (unsigned sho * ow, in x, in len)
{
unsigned sho * emp = (unsigned sho *)calloc(len,
sizeo (unsigned sho ));
in i;
#p agma acc pa allel loop independen
o (i = 0; i < len; i++)
{
emp[(i + x) % len] = ow[i];
}
e u n emp;
}
Código 83
• Make_ma ix: es a unción ecibe como pa áme os ilas, columnas, un ec o y
un núme o de posiciones. P ocede a de ol e una ma iz bina ia ci cula . Se
pa aleliza el bucle de la unción po que al se los elemen os de la ma iz
independien es, se pueden di idi en múl iples hilos de ejecución y cada uno
puede abaja en secciones di e en es del bucle.
bin_ma ix make_ma ix(in ows, in cols, unsigned sho * ec, in x)
{
bin_ma ix ma = ma _ini ( ows, cols);
se _ma ix_ ow(ma , 0, ec);
in i;
#p agma acc pa allel loop independen
o (i = 1; i < ows; i++)
{
ec = shi ( ec, x, cols);
se _ma ix_ ow(ma , i, ec);
}
e u n ma ;
}
Código 84
• Splice: es a unción ecibe como pa áme os un alo mínimo, un alo máximo
y una ila. P ocede a de ol e una ila o mada po los da os de la ila pasada
como pa áme o y limi ada po los alo es máximo y mínimo. Se pa aleliza el
bucle de la unción po que al se los elemen os de la ma iz independien es, se
91
pueden di idi en múl iples hilos de ejecución y cada uno puede abaja en
secciones di e en es del bucle.
unsigned sho * splice(unsigned sho * ow, in min, in max)
{
unsigned sho * emp = (unsigned sho *)calloc(max - min,
sizeo (unsigned sho ));
in i;
#p agma acc pa allel loop independen
o (i = min; i < max; i++)
{
emp[i - min] = ow[i];
}
e u n emp;
}
Código 85
• Pa i y_check_ma ix: es a unción ecibe como pa áme o un código MDPC y
p ocede a c ea la ma iz de pa idad. Se pa aleliza el bucle de la unción po que
al se los elemen os de la ma iz independien es, se pueden di idi en múl iples
hilos de ejecución y cada uno puede abaja en secciones di e en es del bucle.
bin_ma ix pa i y_check_ma ix(mdpc code)
{
clock_ s a , end;
double cpu_ ime_used;
s a = clock();
bin_ma ix H = make_ma ix(code->p, code->p, splice(code-> ow, 0,
code->p), 1);
in i;
#p agma acc pa allel loop independen
o (i = 1; i < code->n0; i++)
{
bin_ma ix M = make_ma ix(code->p, code->p, splice(code-> ow, i
* code->p, (i + 1) * code->p), 1);
H = conca _ho izon al(H, M);
}
end = clock();
cpu_ ime_used = ((double) (end - s a ))/ CLOCKS_PER_SEC;
p in ("Time o H: % n", cpu_ ime_used);
e u n H;
}
Código 86
• Gene a o _ma ix: es a unción ecibe como pa áme o un código MDPC y
p ocede a c ea la ma iz gene ado a. Se pa aleliza el bucle de la unción po que
al se los elemen os de la ma iz independien es, se pueden di idi en múl iples
hilos de ejecución y cada uno puede abaja en secciones di e en es del bucle.
92
bin_ma ix gene a o _ma ix(mdpc code)
{
clock_ s a , end;
double cpu_ ime_used;
s a = clock();
bin_ma ix H = pa i y_check_ma ix(code);
p in ("Cons uc ion o G s a ed... n");
bin_ma ix H_in = ci c_ma ix_in e se(make_ma ix(code->p, code-
>p, splice(code-> ow, (code->n0 - 1) * code->p, code->n), 1));
bin_ma ix H_0 = make_ma ix(code->p, code->p, splice(code-> ow,
0, code->p), 1);
bin_ma ix Q = anspose(ma ix_mul (H_in , H_0));
bin_ma ix M;
in i;
#p agma acc pa allel loop independen
o (i = 1; i < code->n0 - 1; i++)
{
M = make_ma ix(code->p, code->p, splice(code-> ow, i * code->p,
(i + 1) * code->p), 1);
M = anspose(ma ix_mul (H_in , M));
Q = conca _ e ical(Q, M);
}
bin_ma ix I = ma _ini (code->k, code->k);
make_inden i y(I);
bin_ma ix G = conca _ho izon al(I, Q);
cpu_ ime_used = ((double) (end - s a ))/ CLOCKS_PER_SEC;
p in ("Time o G: % n", cpu_ ime_used);
p in ("Gene a o ma ix gene a ed.... n");
e u n G;
}
Código 87
• Ge _max: es a unción ecibe como pa áme os un ec o y una longi ud y
p ocede a de ol e elemen o del ec o con el máximo alo . Se pa aleliza el
bucle de la unción po que al se los elemen os de la ma iz independien es se
pueden di idi en múl iples hilos de ejecución y cada uno puede abaja en
secciones di e en es del bucle.
in ge _max(in * ec, in len)
{
in max = ec[0];
in i;
#p agma acc pa allel loop independen
93
o (i = 1; i < len; i++)
{
i ( ec[i] > max)
{
max = ec[i];
}
}
e u n max;
}
Código 88
• Decode: es a unción ecibe como pa áme os una ma iz bina ia y un código
MDPC y p ocede a de ol e la ma iz decodi icada. Los es p ime os bucles se
ejecu an en pa alelo de o ma independien e pe mi iendo di idi los da os en
múl iples hilos pe mi iendo hace la ejecución de o ma más ápida. El cua o
bucle se ejecu a de o ma secuencial ya que los da os dependen del e ce bucle.
El quin o bucle se ejecu a en pa alelo de o ma independien e pe mi iendo
di idi los da os en múl iples hilos pa a hace la ejecución de o ma más ápida.
bin_ma ix decode(bin_ma ix wo d, mdpc code)
{
bin_ma ix H = pa i y_check_ma ix(code);
bin_ma ix syn = ma ix_mul (H, anspose(wo d));
in limi = 10;
in del a = 5;
in i,j,k,x;
#p agma acc pa allel loop independen
o (i = 0; i < limi ; i++)
{
in unsa is ied[wo d->cols];
#p agma acc pa allel loop independen
o (x = 0; x < wo d->cols; x++)
{
unsa is ied[x] = 0;
}
#p agma acc pa allel loop independen
o (j = 0; j < wo d->cols; j++)
{
#p agma acc loop seq
o (k = 0; k < H-> ows; k++)
{
i (ge _ma ix_elemen (H, k, j) == 1)
{
i (ge _ma ix_elemen (syn, k, 0) == 1)
{
unsa is ied[j] = unsa is ied[j] + 1;
}
94
}
}
}
in b = ge _max(unsa is ied, wo d->cols) - del a;
#p agma acc pa allel loop independen
o (j = 0; j < wo d->cols; j++)
{
i (unsa is ied[j] >= b)
{
se _ma ix_elemen (wo d, 0, j,
(ge _ma ix_elemen (wo d, 0, j) ^ 1));
syn = add_ma ix(syn, ma _splice(H, 0, H-> ows - 1, j,
j));
}
}
i (is_ze o_ma ix(syn))
{
e u n wo d;
}
}
p in ("Decoding ailu e... n");
exi (0);
}
Código 89
4.2. Segunda onda de mejo as
Después de ealiza las p ime as mejo as sob e la pa alelización del código del Classic
McEliece se ha ealizado una segunda onda pa a in en a mejo a la e iciencia del
código y mejo a el endimien o de la ejecución del código.
Las unciones que han sido mejo adas son las siguien es:
4.2.1. ma ix.c
• Se _ma ix_ ow: la mejo a ealizada en es a unción consis e en añadi una
nue a di ec i a po encima. Es a es ‘da a p esen ’ que asegu a que los da os de
las ma ices A y ec es én p esen es y accesibles en la egión pa alela. Es o
ga an iza que los da os necesa ios es én disponibles pa a la ejecución pa alela.
oid se _ma ix_ ow(bin_ma ix A, in ow, unsigned sho * ec)
{
i ( ow < 0 || ow >= A-> ows)
{
p in ("Row index ou o ange n");
exi (0);
}
#p agma acc da a p esen (A, ec)
95
{
#p agma acc pa allel loop independen
o (in i = 0; i < A->cols; i++)
{
se _ma ix_elemen (A, ow, i, ec[i]);
}
}
}
Código 90
• Ma ix_ e : en es a unción se ha añadido una di ec i a ‘da a p esen ’ que
ealiza la misma ope ación que la di ec i a u ilizada en se _ma ix_ ow.
bin_ma ix ma ix_ e (bin_ma ix A)
{
in lead = 0;
in ow_coun = A-> ows;
in col_coun = A->cols;
bin_ma ix emp = ma _ini ( ow_coun , col_coun );
emp = ma _copy(A);
in = 0;
#p agma acc da a p esen ( emp)
{
while( < ow_coun )
{
i (ma _elemen ( emp, , ) == 0)
{
in i;
#p agma acc pa allel loop independen
o (i = + 1; i < emp-> ows; i++)
{
i (ma _elemen ( emp, i, ) == 1)
{
swap( emp, , i);
b eak;
}
}
i (i == ow_coun )
{
p in ("Ma ix canno be ans o med in o ow echlon
o m...");
exi (1);
}
}
else
{
#p agma acc pa allel loop independen
96
o (in i = 0; i < ow_coun ; i++)
{
i (ma _elemen ( emp, i, ) == 1 && i != )
{
add_ ows( emp, , i);
}
}
++;
}
}
}
e u n emp;
}
Código 91
4.2.2. qc_mdpc.c
• qc_mdpc_ini : en es a unción se ha añadido una di ec i a simple de pa allel loop
que pa aleliza el bucle while y c ea múl iples hilos o unidades de p ocesamien o
pa a ejecu a las i e aciones en pa alelo.
mdpc qc_mdpc_ini (in n0, in p, in w, in )
{
mdpc code;
code = (mdpc)sa e_malloc(sizeo (s uc qc_mdpc));
code->n0 = n0;
code->p = p;
code->w = w;
code-> = ;
code->n = n0 * p;
code-> = p;
code->k = (n0 - 1) * p;
unsigned seed;
code-> ow = (unsigned sho *)calloc(n0 * p, sizeo (unsigned sho ));
p in ("Inpu seed o -1 o use de aul seed: ");
scan ("%u", &seed);
ime_ x;
i (seed == -1)
{
s and((unsigned) ime(& x));
}
else
{
s and(seed);
}
while(1)
{
in lag = 0;
97
in idx;
#p agma acc pa allel loop
while( lag < w)
{
idx = andom_ al(0, (n0 * p) - 1, seed);
i (!code-> ow[idx])
{
code-> ow[idx] = 1;
lag = lag + 1;
}
}
i ((ge _ ow_weigh (code-> ow, (n0 - 1) * p, (n0 * p)-1)) % 2 ==
1)
{
b eak;
}
ese _ ow(code-> ow, 0, n0 * p);
}
p in ("MDPC code gene a ed.... n");
e u n code;
}
Código 92
• ge _ ow_weigh : en es a unción se ha modi icado la di ec i a an e io . Se ha
eliminado la pa e de ‘independen ’ y se ha añadido la pa e de ‘gang ec o ’.
Es a pa e de la di ec i a indica que cada "gang" se di ide en " ec o " unidades,
que son básicamen e los hilos indi iduales o unidades de p ocesamien o que
ealizan las ope aciones ec o iales.
in ge _ ow_weigh (unsigned sho * ow, in min, in max)
{
in weigh = 0;
in i;
#p agma acc pa allel loop gang ec o
o (i = min; i < max + 1; i++)
{
i ( ow[i] == 1)
{
weigh ++;
}
}
e u n weigh ;
}
Código 93
• ese _ ow: en es a unción se han ealizado los mismos cambios que en la
unción “ge _ ow_weigh ”.
oid ese _ ow(unsigned sho * ow, in min, in max)
98
{
in i;
#p agma acc pa allel loop gang ec o
o (i = min; i < max + 1; i++)
{
ow[i] = 0;
}
}
Código 94
• pa i y_check_ma ix: en es a unción se ha añadido una nue a di ec i a llamada
‘da a’. Es a di ec i a asegu a que la ma iz H es é disponible pa a la copia de
salida después de que inalice la egión pa alela. También c ea una a iable i en
el disposi i o (GPU) pa a que es é disponible en la egión pa alela.
bin_ma ix pa i y_check_ma ix(mdpc code)
{
clock_ s a , end;
double cpu_ ime_used;
s a = clock();
bin_ma ix H = make_ma ix(code->p, code->p, splice(code-> ow, 0,
code->p), 1);
in i;
#p agma acc da a copyou (H) c ea e(i)
{
#p agma acc pa allel loop independen educ ion(conca :H)
o (i = 1; i < code->n0; i++)
{
bin_ma ix M = make_ma ix(code->p, code->p, splice(code-
> ow, i * code->p, (i + 1) * code->p), 1);
H = conca _ho izon al(H, M);
}
}
end = clock();
cpu_ ime_used = ((double) (end - s a ))/ CLOCKS_PER_SEC;
p in ("Time o H: % n", cpu_ ime_used);
e u n H;
}
Código 95
• gene a o _ma ix: en es a unción se ha añadido una nue a cláusula en la
di ec i a que iene. La cláusula ‘ educ ion (conca : Q)’ especi ica que la a iable
Q se educi á (conca ena á) de mane a segu a en pa alelo. Es o signi ica que
cada hilo calcula una pa e del esul ado inal y, al inal del bucle, los esul ados
99
pa ciales se combinan pa a o ma el esul ado global de la conca enación de
ma ices.
bin_ma ix gene a o _ma ix(mdpc code)
{
clock_ s a , end;
double cpu_ ime_used;
s a = clock();
bin_ma ix H = pa i y_check_ma ix(code);
p in ("Cons uc ion o G s a ed... n");
bin_ma ix H_in = ci c_ma ix_in e se(make_ma ix(code->p, code->p,
splice(code-> ow, (code->n0 - 1) * code->p, code->n), 1));
bin_ma ix H_0 = make_ma ix(code->p, code->p, splice(code-> ow, 0,
code->p), 1);
bin_ma ix Q = anspose(ma ix_mul (H_in , H_0));
bin_ma ix M;
in i;
#p agma acc pa allel loop independen educ ion(conca :Q)
o (i = 1; i < code->n0 - 1; i++)
{
M = make_ma ix(code->p, code->p, splice(code-> ow, i * code->p, (i
+ 1) * code->p), 1);
M = anspose(ma ix_mul (H_in , M));
Q = conca _ e ical(Q, M);
}
bin_ma ix I = ma _ini (code->k, code->k);
make_inden i y(I);
bin_ma ix G = conca _ho izon al(I, Q);
end = clock();
cpu_ ime_used = ((double) (end - s a ))/ CLOCKS_PER_SEC;
p in ("Time o G: % n", cpu_ ime_used);
p in ("Gene a o ma ix gene a ed.... n");
e u n G;
}
Código 96
• ge _max: en es a unción se han ealizado las mismas mejo as que en la unción
“gene a o _ma ix”.
in ge _max(in * ec, in len)
{
in max = ec[0];
in i;
#p agma acc pa allel loop independen educ ion(max)
o (i = 1; i < len; i++)
106
e o es y el algo i mo de Euclides se enca ga de calcula el máximo común
di iso en e dos polinomios.
El obje i o de nues a implemen ación es mejo a la e iciencia al ealiza una
pa alelización en GPU y la o a implemen ación se cen a en mejo a la e iciencia
mejo ando la segu idad del ci ado. En la siguien e abla se mos a án los esul ados
en e las dos implemen aciones.
Con pa alelización
GPU (nues o)
Zynq Ul aScale+
Longi ud del ex o
a ci a
512 ca ac e es
512 ca ac e es
Tamaño de las
cla es
1000 bi s cla e
pública y 2000 bi s
cla e p i ada
1046739 by es
cla e pública y
2093478 by es
cla e p i ada
Tiempo de c ea la
ma iz H y ealiza
el ci ado
2961 ms
1.5 ms
Tiempo de c ea la
ma iz G y ealiza
el desci ado
44873 ms
1002.1 ms
Tiempo o al de la
ejecución del
p oceso
46490 ms
1010 ms
La úl ima in es igación [21] u ilizada pa a compa a con nues a implemen ación iene
una modi icación híb ida dis ibuida en dos pa es. La p ime a pa e aumen a la asa de
in o mación añadiendo da os en el pa ón de e o es y la segunda pa e disminuye el
amaño de la cla e pública u ilizando una ma iz gene a iz que iene una ila en o ma
echelon. Al se un sis ema híb ido u iliza dis in os mé odos pa a pode gene a las
cla es y pa a pode ealiza los p ocesos de ci ado y desci ado. En nues a
implemen ación enemos dos pa áme os iniciales pa a c ea el QC-MDPC McEliece, en
cambio en la o a implemen ación se usan solo dos pa áme os alea o ios iniciales pa a
gene a las cla es. Las p uebas de la implemen ación híb ida se han ealizado sob e un
p ocesado In el Co e 2 y un compilado de In el con un sis ema ope a i o de 32 bi s. El
obje i o de la implemen ación híb ida es mejo a la segu idad en e a los a aques e
in en a disminui el amaño de las cla es pa a que sea más e icien e. El obje i o es
simila al de nues a implemen ación que in en a mejo a la e iciencia ealizando una
pa alelización en GPU. En la siguien e abla se mues an una compa ación en e las dos
implemen aciones.
107
Con pa alelización
GPU (nues o)
In el Co e 2
Longi ud del ex o
a ci a
1320 ca ac e es
No se sabe
Tamaño de las
cla es
1000 bi s cla e
pública y 2000 bi s
cla e p i ada
32000 by es cla e
pública y 64000
by es cla e p i ada
Tiempo de c ea la
ma iz H y ealiza
el ci ado
22 ms
2.19 ms
Tiempo de c ea la
ma iz G y ealiza
el desci ado
644 ms
75 ms
Tiempo o al de la
ejecución del
p oceso
698 ms
79 ms
Las azones po las que c eemos que es e algo i mo p esen a es e endimien o an
bueno son las siguien es:
• Uso de códigos QC-MDPC, pe mi en ealiza ci ados u ilizando
implemen aciones con una huella de ecu sos más pequeña de lo no mal.
• Pe mi e educi el amaño de las cla es públicas, lo que pe mi e c ea diseños
más pequeños.
• Uso de ha dwa e, FPGAs y implemen aciones.
Como se puede obse a los esul ados que hemos ob enido en nues a implemen ación
se asemejan a los esul ados que se han ob enido en o as implemen aciones usando
o as écnicas y mé odos pa a ob ene los, ya sea con o o ha dwa e, usando o os
algo i mos o usando o os pa áme os de mayo amaño.
5.3. Compa aciones adicionales
En es e apa a ado abo da emos una compa ación en e nues a implemen ación con y
sin pa aleliza y los algo i mos adicionales RSA y DH, pa a e cuán o oscilan los
iempos de ejecución pa iendo de un mismo ex o de 100 ca ac e es. Pa a ello hemos
u ilizado el siguien e ex o: Hoy es lunes. y mi casa es á a media ho a de Mad id, po lo
que end emos que coge el bus pa a i .
Pa a nues as implemen aciones hemos ealizado una ejecución siguiendo las
ins ucciones desc i as n en la sección 5.1 de es e documen o, pa a ello in oduci emos
dicho ex o y un alo de semilla igual a 1. Pa a comp oba que nues o código
pa alelizado unciona enemos que comp oba que al ejecu a lo se ob iene el mismo
ex o ci ado que con el algo i mo McEliece o iginal, pa a ello se ha ealizado un olcado
108
a mano en un iche o bina io. Pos e io men e han sido compa ados con un p og ama
de compa ación de iche os (Di Me ge).
En el caso de RSA y DH se ha u ilizado una máquina i ual de Debian (32-bi ). Con es a
máquina i ual se ha empleado OpenSSL pa a la c eación de las cla es y ci ado y
desci ado del ex o. En el caso de DH se mues a el iempo que a da únicamen e en
c ea las cla es necesa ias pa a lle a a cabo el p oceso con y sin gene ación de
pa áme os, ya que es e algo i mo no ealiza ci ado/desci ado. Pa a ealiza es as
compa a i as y e los iempos esul an es hemos ealizado los siguien es sc ip s:
• RSA
s a =`da e +%s%N`
openssl pkeyu l -enc yp -pubin -inkey sapubkey.pem -in ex o. x -ou enc.bin
openssl pkeyu l -dec yp -inkey sakey.pem -in enc.bin -ou plainagain. x
end=`da e +%s%N`
echo `exp $end - $s a `
En es e sc ip , p ime o se inicia la cuen a del eloj. Luego, se c ea la cla e p i ada
y la cla e pública a pa i de la p i ada. Y po úl imo se mues a el iempo.
s a =`da e +%s%N`
openssl genpkey -algo i hm sa -ou sakey.pem
openssl pkey -pubou -in sakey.pem -ou sapubkey.pem
end=`da e +%s%N`
echo `exp $end - $s a `
En es e sc ip , p ime o se inicia la cuen a del eloj. Luego se ci a y se desci a. Y
po úl imo se mues a el iempo.
• DH (gene ando pa áme os)
s a =`da e +%s%N`
openssl genpkey -genpa am -algo i hm dh -ou dhpa am.pem
openssl genpkey -pa am ile dhpa am.pem -ou dhkey1.pem
openssl pkey -pubou -in dhkey1.pem -ou dhpubkey1.pem
openssl genpkey -pa am ile dhpa am.pem -ou dhkey2.pem
openssl pkey -pubou -in dhkey2.pem -ou dhpubkey2.pem
openssl pkeyu l -de i e -inkey dhkey1.pem -pee key dhpubkey2.pem -ou
sec e 1
openssl pkeyu l -de i e -inkey dhkey2.pem -pee key dhpubkey1.pem -ou
sec e 2
cmp sec e 1 sec e 2
end=`da e +%s%N`
echo `exp $end - $s a `
En es e sc ip , p ime o se inicia la cuen a del eloj. Luego, se c ean los
pa áme os que compa i án ambos usua ios, las cla es p i adas a pa i de los
pa áme os y las cla es públicas a pa i de las cla es p i adas. Después se
gene a la cla e simé ica que usa án ambos usua ios pa a ci a . Y po úl imo, se
mues a el iempo.
109
• DH (pa áme os ya gene ados)
s a =`da e +%s%N`
openssl genpkey -pa am ile dhpa am.pem -ou dhkey1.pem
openssl pkey -pubou -in dhkey1.pem -ou dhpubkey1.pem
openssl genpkey -pa am ile dhpa am.pem -ou dhkey2.pem
openssl pkey -pubou -in dhkey2.pem -ou dhpubkey2.pem
openssl pkeyu l -de i e -inkey dhkey1.pem -pee key dhpubkey2.pem -ou
sec e 1
openssl pkeyu l -de i e -inkey dhkey2.pem -pee key dhpubkey1.pem -ou
sec e 2
cmp sec e 1 sec e 2
end=`da e +%s%N`
echo `exp $end - $s a `
En es e sc ip , p ime o se inicia la cuen a del eloj. Luego se c ean las cla es
p i adas a pa i de los pa áme os (se supone que ya han sido c eados) y las
cla es públicas a pa i de las p i adas. Después se c ea la cla e simé ica que
usa án ambos usua ios pa a ci a . Y, po úl imo, se mues a el iempo.
ALGORITMO
NUESTRO NO
PARALELIZADO
NUESTRO
PARALELIZADO
RSA
DH
TIEMPO
Gene ación
Cla es (s)
3.71763
0.218176
0,62763
385,24985
(con
gene ación de
pa áme os)
0,21538 (sin
gene ación de
pa áme os)
TIEMPO
CIFRADO Y
DESCIFRADO
(suma)
0.10131
0.02961
0,05563
NO CIFRA,
USADO PARA
INTERCAMBIO
DE CLAVES
Tabla 5: iempos di e en es McEliece, RSA y DH
En la Tabla 5, podemos obse a que nues a implemen ación de McEliece es mucho
más ápida que la del algo i mo RSA en la gene ación de cla es y muy pa ecida a la de
Di ie-Hellman. Además, nues a implemen ación compa ada con la RSA a la ho a de
ci a /desci a es más ápida.
110
6.Apo aciones y Conclusiones
6.1. Apo aciones
Las apo aciones ealizadas po Pe a I ano du an e el desa ollo del T abajo Fin de
G ado han sido la búsqueda, análisis, compa ación y p uebas de las implemen aciones
sob e el algo i mo pos -cuán ico de Classic McEliece. Es e p oceso implicó iden i ica
e siones uncionales del algo i mo y comp ende a ondo su uncionamien o. P ime o
ealizó una búsqueda exhaus i a pa a encon a dis in as e siones álidas del algo i mo
con ins ucciones sob e su uncionamien o. Pos e io men e ealizó nume osas p uebas
en e las dis in as implemen aciones pa a compa a los esul ados en e ellas y obse a
qué implemen ación o ecía el esul ado más e icien e. Una ez escogida la mejo
implemen ación explicó po qué se había escogido esa implemen ación pa a ealiza las
modi icaciones sob e ella. Pe a p ocedió a ealiza una mejo a sob e el código
aplicando el lenguaje de p og amación OpenACC. Después de comple a las
modi icaciones sob e el código, ca gó odos los a chi os en el emulado de p ueba de
Google Colab. A a és de una se ie de comandos log ó ca ga los iche os necesa ios,
compila el código pa a la e sión pa alelizada (op imizada) y la e sión o iginal y
pos e io men e ejecu a el código. Una ez comple adas las p uebas necesa ias, Pe a
analizó los iempos ob enidos pa a ambas e siones (la op imizada y la o iginal),
iden i icando cla amen e la mejo a de endimien o log ada en la e sión mejo ada.
Pos e io men e, Pe a se en ocó en mejo a aún más el código pa alelizado en la e sión
op imizada de la implemen ación. Median e la ealización de p uebas y análisis,
demos ó una ez más una no able mejo a en el iempo espec o a las o as dos
e siones y explicó po qué se había p oducido esa mejo a en la segunda e sión
espec o a las o as.
En una e apa pos e io , Pe a ealizó una de allada compa ación en e la
implemen ación mejo ada y o as in es igaciones simila es. Es a compa ación si ió
pa a alida que los esul ados ob enidos en la segunda e sión mejo ada es aban en la
misma línea con los log os de o as in es igaciones. Además, delineó de mane a cla a
las di e encias en e la implemen ación mejo ada y las o as in es igaciones an o en
ha dwa e como en so wa e.
Pe a ambién con ibuyó en la explicación de los mé odos y unciones que se
encuen an en el código de la implemen ación. Además, c eó diag amas que ilus an el
lujo de uncionamien o y las llamadas que ealiza cada mé odo en el código. También
p opo cionó una comp ensión más p o unda de las mejo as ealizadas en el código
o iginal, incluyendo el uncionamien o del código pa alelizado con lenguaje OpenACC.
Finalmen e, Pe a con ibuyó ac i amen e en la búsqueda de in o mación sob e la
úl ima anda de algo i mos del concu so o ganizado po NIST. Además, se enca gó de la
c eación del esumen, la explicación de los obje i os y supe isó de ce ca la plani icación
111
du an e odo el pe íodo de desa ollo del T abajo Fin de G ado. También elabo ó una
abla de allada que esume las ac i idades ealizadas en cada pe íodo de abajo.
En e las apo aciones ealizadas po Víc o Mo eno du an e el desa ollo del T abajo
Fin de G ado se encuen an la c eación del esumen, la in oducción, la explicación de
los obje i os, el es ado del a e y supe isó la plani icación du an e odo el pe íodo de
desa ollo del T abajo Fin de G ado median e la elabo ación de una abla de allada que
esume las ac i idades ealizadas en cada pe íodo de abajo. Además, se enca gó de la
búsqueda y análisis de los algo i mos NIST pa a la edacción de cada uno de ellos y
pos e io men e pode elegi el algo i mo en el que cen a nos. Se enca gó ac i amen e
de la co ección, e isión y mejo a cons an e de la edacción y aducción de la memo ia.
Asimismo, se enca gó de la búsqueda, análisis, compa ación y p uebas de las
implemen aciones sob e el algo i mo pos -cuán ico de Classic McEliece. Es e p oceso
consis ió como hemos dicho en el pá a o an e io en iden i ica e siones uncionales
del algo i mo y comp ende a ondo su uncionamien o. P ime o ealizó una búsqueda
exhaus i a pa a encon a dis in as e siones del algo i mo que uncionasen y que
u ie an ins ucciones sob e cómo uncionan esas implemen aciones. Pos e io men e
ealizó nume osas p uebas en e las dis in as implemen aciones pa a compa a los
esul ados en e ellas y obse a que implemen ación o ecía el esul ado más e icien e.
Una ez escogida la mejo implemen ación explicó po que se había escogido esa
implemen ación pa a ealiza las mejo as sob e ella. Asis ió a Pe a en algunas pa es de
la pa alelización y lle ó a cabo jun o a Pe a la oma de los iempos ob enidos pa a
ambas e siones (la mejo ada y la o iginal), iden i icando cla amen e la mejo a de
endimien o log ada en la e sión mejo ada, an o la p ime a como la segunda.
En una e apa pos e io , Víc o ealizó una de allada compa ación en e la
implemen ación desca gada, la mejo ada, RSA y DH. Pa a ello, u o que desca ga se una
máquina i ual en la que ealizó sc ip s de bash pa a pode medi el iempo empleado
po los algo i mos RSA y DH. Po o o lado, ejecu ó las implemen aciones en Google
Collab y median e un ex o de igual amaño iden i icó las di e encias en los iempos de
gene ación de cla es y ci ado que su gían en e ellas.
Finalmen e, Víc o ambién con ibuyó en la edacción de los mé odos y unciones que
se encuen an en el código de la implemen ación. También p opo cionó una
comp ensión más p o unda de las mejo as ealizadas en el código o iginal, incluyendo
el uncionamien o del código pa alelizado con lenguaje OpenACC.
6.2. Conclusiones
Es e T abajo de Fin de G ado se ha cen ado en el es udio de la impo ancia de la
compu ación cuán ica, los dis in os c ip osis emas del p og ama lanzado po NIST y
especialmen e en el Classic McEliece.
Hemos log ado implemen a de o ma pa alela uno de los algo i mos inalis as de la
con oca o ia del Na ional Ins i u e o S anda s and Technology de Es ados Unidos (NIST)
y modi ica el código pa a que ome mensajes po consola y los con ie a a bina io pa a
112
su pos e io ci ado y desci ado (en la implemen ación o iginal e an mensajes
p ede inidos en bina io de un amaño es ánda ). De es as op imizaciones hemos
conseguido saca una mejo a de endimien o muy buena.
Además, hemos sido capaces de analiza y compa a el endimien o de las dis in as
implemen aciones buscadas y es udiadas an e io men e. Asimismo, las hemos
analizado y compa ado con o as in es igaciones y con RSA y DH. Es e abajo de lec u a
y análisis ha se ido de u ilidad pa a se más conscien es del g an po encial que iene el
sis ema de McEliece, sis ema que se ha es udiado du an e muchos años y siemp e ha
ob enido buenos esul ados a la ho a de p opo ciona segu idad.
Pa a conclui , la segu idad de la in o mación de las comunicaciones iene una g an
impo ancia ya que cualquie pe sona ealiza mul i ud de comunicaciones dia ias las
cuales con ienen en ocasiones in o mación sensible y/o p i ada. La amenaza que
supone la compu ación cuán ica a siendo cada ez más ce cana debido al c ecimien o
cada ez mayo del endimien o de los o denado es. Po ello, la c ip og a ía pos -
cuán ica como u u a solución debe ía cob a más impo ancia, es deci , se debe ían
dedica más ecu sos en la búsqueda y/o mejo a de algo i mos pa a pode log a una
mayo di icul ad a la ho a de pode ompe los.
6.3. Obje i os u u os
Como hemos dicho, la c ip og a ía no ha hecho nada más que comenza . Se a a de un
e eno en desa ollo al que le queda eco ido.
Noso os hemos plan eado es udia el McEliece del que hemos sacado buenas
conclusiones. Sin emba go, es posible que haya algunos mejo es y con enga es udia los
o que después de la en ega de es e T abajo de Fin de G ado, salgan o se ba ajeen
mejo es opciones.
Po lo que, hab ía que segui es udiando aquellos candida os del NIST y mejo a los pa a
e cuál pod ía llega a se su e dade o po encial.
113
6. Con ibu ions and Conclusions
6.1. Con ibu ions
The con ibu ions made by Pe a I ano du ing he de elopmen o he Bachelo 's Thesis
in ol ed he sea ch, analysis, compa ison, and es ing o implemen a ions o he pos -
quan um Classic McEliece algo i hm. This p ocess en ailed iden i ying unc ional
e sions o he algo i hm and gaining a deep unde s anding o i s ope a ion. Pe a
ini ially conduc ed an exhaus i e sea ch o ind di e en e sions o he algo i hm ha
we e unc ional and had ins uc ions on how hese implemen a ions wo ked.
Subsequen ly, he ca ied ou nume ous es s among he di e en implemen a ions o
compa e he esul s and de e mine which implemen a ion p o ided he mos e icien
ou come. Once he bes implemen a ion was chosen, he explained why i was selec ed
o u he imp o emen s. Pe a hen p oceeded o enhance he code using he
OpenACC p og amming language. A e comple ing he code modi ica ions, he uploaded
all he iles o he Google Colab emula o . Th ough a se ies o commands, he managed
o load he necessa y iles, compile he code o he pa allelized (imp o ed) e sion and
he o iginal e sion, and subsequen ly un he code. A e comple ing he necessa y
es s, Pe a analyzed he imes ob ained o bo h e sions ( he op imized and he
o iginal), clea ly iden i ying he pe o mance imp o emen achie ed in he enhanced
e sion.
Subsequen ly, Pe a ocused on u he enhancing he pa allelized code in he imp o ed
e sion o he implemen a ion. Th ough es ing and analysis, he once again
demons a ed a signi ican imp o emen in he ime compa ed o he o he wo
e sions and explained why his imp o emen had occu ed in he second e sion
compa ed o he o he s.
In a la e s age, Pe a conduc ed a de ailed compa ison be ween he imp o ed
implemen a ion and simila esea ch e o s. This compa ison se ed o alida e ha he
esul s ob ained in he second imp o ed e sion we e in line wi h he achie emen s o
o he esea ch endea o s. Fu he mo e, he clea ly ou lined he dis inc ions be ween
he imp o ed implemen a ion and he o he esea ch e o s, bo h in e ms o ha dwa e
and so wa e.
Pe a also con ibu ed o explaining he me hods and unc ions ound in he
implemen a ion code. Addi ionally, he c ea ed diag ams illus a ing he low o
ope a ion and he calls made by each me hod in he code. He also p o ided a deepe
unde s anding o he enhancemen s made o he o iginal code, including he ope a ion
o he pa allelized code using OpenACC language.
Finally, Pe a ac i ely con ibu ed o he sea ch o in o ma ion abou he la es ba ch
o algo i hms in he compe i ion o ganized by NIST. Addi ionally, he was esponsible o
c ea ing he summa y, explaining he objec i es, and closely o e seeing he planning
114
h oughou he en i e de elopmen pe iod o he Bachelo 's Thesis. He also compiled a
de ailed able summa izing he ac i i ies pe o med in each wo k pe iod.
Among he con ibu ions made by Víc o Mo eno du ing he de elopmen o he
Bachelo 's Thesis, we ind he c ea ion o he abs ac , in oduc ion, explana ion o he
objec i es, he s a e o he a , and he supe ision o he planning h oughou he en i e
de elopmen pe iod o he Bachelo 's Thesis by c ea ing a de ailed able summa izing
he ac i i ies ca ied ou in each wo k pe iod. Addi ionally, he was esponsible o he
sea ch and analysis o NIST algo i hms o d a ing each o hem and subsequen ly being
able o choose he algo i hm o ocus on. He ac i ely ook ca e o he co ec ion, e iew,
and cons an imp o emen o he w i ing and ansla ion o he epo .
Fu he mo e, he was in cha ge o he sea ch, analysis, compa ison, and es ing o
implemen a ions o he pos -quan um Classic McEliece algo i hm. This p ocess, as
men ioned in he p e ious pa ag aph, in ol ed iden i ying unc ional e sions o he
algo i hm and ho oughly unde s anding i s ope a ion. He i s conduc ed an exhaus i e
sea ch o ind di e en e sions o he algo i hm ha wo ked and had ins uc ions on
how hese implemen a ions unc ioned. He hen conduc ed nume ous es s among he
di e en implemen a ions o compa e he esul s be ween hem and obse e which
implemen a ion o e ed he mos e icien esul . Once he bes implemen a ion was
chosen, he explained why ha implemen a ion had been chosen o u he
imp o emen s. He assis ed Pe a in some pa s o pa alleliza ion and oge he wi h
Pe a , eco ded he imes ob ained o bo h e sions ( he imp o ed and he o iginal),
clea ly iden i ying he pe o mance imp o emen achie ed in he imp o ed e sion,
bo h he i s and he second.
In a la e s age, Víc o conduc ed a de ailed compa ison be ween he downloaded
implemen a ion, he imp o ed one, RSA, and DH. To do his, he had o download a
i ual machine in which he an bash sc ip s o measu e he ime used by he RSA and
DH algo i hms. On he o he hand, he execu ed he implemen a ions in Google Colab
and, using a ex o he same size, iden i ied he di e ences in key gene a ion and
enc yp ion imes ha a ose be ween hem.
Finally, Víc o also con ibu ed o he w i ing o he me hods and unc ions ound in he
implemen a ion code. He p o ided a deepe unde s anding o he imp o emen s made
in he o iginal code, including he ope a ion o he pa allelized code using he OpenACC
language.
6.2. Conclusions
This Bachelo 's Thesis has ocused on he s udy o he impo ance o quan um
compu ing, he di e en c yp osys ems om he p og am launched by he Na ional
Ins i u e o S anda ds and Technology (NIST), and especially on Classic McEliece.
We ha e success ully implemen ed one o he inalis algo i hms om he call by he
Na ional Ins i u e o S anda ds and Technology (NIST) in a pa allel manne . Addi ionally,
we modi ied he code o accep console inpu messages and con e hem o bina y o
115
subsequen enc yp ion and dec yp ion (in he o iginal implemen a ion, messages we e
p ede ined in bina y o a s anda d size). These enhancemen s ha e esul ed in a
signi ican pe o mance imp o emen .
Fu he mo e, we ha e been able o analyze and compa e he pe o mance o he
a ious implemen a ions ha we e esea ched and s udied ea lie . Addi ionally, we
e alua ed hem in compa ison o o he esea ches and alongside RSA and DH. This
p ocess o eading and analysis has been ins umen al in making us mo e awa e o he
emendous po en ial ha he McEliece sys em holds, a sys em ha has been s udied
o many yea s and has consis en ly demons a ed s ong secu i y capabili ies.
In conclusion, he secu i y o communica ion in o ma ion holds g ea impo ance, as
indi iduals engage in nume ous daily communica ions ha o en con ain sensi i e
and/o p i a e in o ma ion. The h ea posed by quan um compu ing is becoming
inc easingly imminen due o he e e -g owing pe o mance o compu e s. The e o e,
pos -quan um c yp og aphy, as a u u e solu ion, should be gi en g ea e emphasis. This
means dedica ing mo e esou ces o he sea ch and/o imp o emen o algo i hms o
achie e g ea e di icul y in b eaking hem.
6.3. Fu u e Objec i es
As we ha e men ioned, c yp og aphy is jus ge ing s a ed. I 's a ield in de elopmen
wi h a long way o go.
We' e chosen o s udy McEliece and ha e d awn posi i e conclusions om i . Howe e ,
he e migh be e en be e op ions ha a e wo h explo ing. I 's possible ha a e he
comple ion o his Bachelo 's Thesis, new and be e al e na i es eme ge o a e
conside ed.
The e o e, i would be essen ial o con inue s udying he NIST candida es and e ine
hem o unde s and hei ue po en ial.