Protocol de Ko-Lee-Cheon-Hang-Park

El protocol Ko-Lee-Hang-Park és un protocol de clau pública que usa grups no abelianos. Va ser propost per Ki Hyoung Ko, Sang Jin Lee, Jung Hee Cheon, Jae Woo Han, Ju-sung Kang i Choonsik Park. Utilisa el fonament de que els grups trena poden servir com una bona font d'enriquiment per a la criptografia, lo que inclou lo següent:

El problema de la paraula és solucionat per mig d'un algoritme ràpit que computa la forma canònica que pot ser manejada de manera eficient per computadors.
Les operacions de grup poden ser eixecutades de manera eficient.
Els grups de trenes tenen alguns problemes matemàtics difícils que poden ser utilisats per a dissenyar primitius criptogràfics.

També té com a fi propondre i implementar un protocol d'acort de clau i sistema criptográfico de clau pública que pot ser utilisat per a dissenyar primitives criptogràfiques. La seguritat d'este sistema està basada en problemes topològics, combinatoris i teòrics de grups que són intractibles d'acort a l'actual coneiximent matemàtic. La fundamentación d'este sistema és diferent a la majoria de criptosistemas usats en teoria de números, pero existixen algunes similituts en el disseny.

Antecedents

Des de que Diffie i Hellman varen presentar per primera volta un criptosistema de clau pública usant funcions d'una sola via, alguns sistemes de sifrat de clau pública han segut vulnerats. Molts dels sistemes de sifrat de clau pública requerixen una gran cantitat de número primo. La dificultat de factorisació de sancers en una gran cantitat de factors primers forma la base del sistema RSA i les seues variants com la de Rabin-Williams, l'esquema de LUC o el sifrat de curva elíptica. També la dificultat del problema d'algoritme discret forma la base dels sifrats tipo Diffie-Hellman com ElGamal.

Hi ha hagut prou esforços per a desenrollar sifrats de clau pública alternatius que no estan basats en la teoria de números. El primer intent va ser usar els problemes de dificultat NP en combinatòria com el sifrat Merkle-Hellman i les seues modificacions. Alguns criptógrafos han segut pessimistes sobre la criptografia combinatòria despuix del dessiframent del sifrat de clau pública tipo Knapsack realisat per Shamir, Brickell, Lagarias, Odlyzko, Vaudenay i uns atres. La majoria dels criptosistemas derivats de la teoria de grups combinatoris són principalment teòrics o tenen certes llimitacions en la pràctica àmplia i general.

Descripció de funcionament

Per a este protocol d'encriptación s'utilisa una funció unidireccional basada en el problema de conjugació en grups trenats, i d'esta funció es derivara un protocol d'establiment de clau i un protocol de clau pública.

Funció unidireccional

Si considerem dos subgrups $L B_{l}$ i $R B_{r}$ que pertanyen a $B_{l + r}$ , tals que $L B_{l}$ són les trenes formades en trenar les trenes esquerres entre $l + r$ , és dir, que les trenes $1, 2, ..., l$ són les úniques que estan trenades, i les trenes $l + 1, l + 2, ..., r$ no ho estan. De forma similar el subgrup $R B_{r}$ són les trenes formades per les trenes trenades de la dreta, és dir que les trenes $l + 1, l + 2, ..., r$ estan trenades, pero les trenes $1, 2, ..., l$ no estan trenades. D'esta forma, cada subgrup es genera aixina:

$L B_{l}$ es genera per σ $_{1}$ , σ $_{2}$ ,..., σ $_{l - 1}$ , i el subgrup $R B_{r}$ es genera per σ $_{l + 1}$ , σ $_{l + 2}$ ,..., σ $_{r - 1}$ .

En la funció també deu considerar-se la propietat conmutativa dels grups trena que diu que σ $_{i}$ σ $_{j} =$ σ $_{j}$ σ $_{i}$ per a $| i - j |$ ≥ $2$ . Aixina, es pot dir que per a qualsevol $a$ Є $L B_{l}$ i $b$ Є $R B_{r}$ , llavors $a b = b a$ . Aixina, es té que la funció és:

$f : L B_{l}$ × $B_{l + r}$ → $B_{l + r}$ × $B_{l + r}$ , $f (a, x) = (a x a^{- 1})$

Esta funció és unidireccional degut a que donats $(a, x)$ és fàcil calcular $a x a^{- 1}$ , pero requerix un temps exponencial per a calcular $a$ coneixent $(a x a^{- 1}, x)$ , i en açò es basa la seguritat d'este protocol criptográfico. En este aspecte és similar al protocol de Diffie-Hellman, ya que el rol de $x$ és similar al de $g$ en el protocol Diffie-Hellman.

Establiment de clau

Pas de preparació: S'elegixen dos sancers $l$ i $r$ tals que la trena $x$ d'orde $l + r$ és suficientment complicada, i després esta es publica.

Pas d'establiment de clau:
- Alice tria un $a$ Є $L B_{l}$ aleatoriamente i li envia $y_{1} = a x a^{- 1}$ a Bob
- Bob tria un $b$ Є $R B_{r}$ aleatoriamente i li envia $y_{2} = b x b^{- 1}$ a Alice
- Alice rep $y_{2}$ i calcula la clau compartida $K = a y_{2} a^{- 1}$
- Bob rep $y_{1}$ i calcula la clau compartida $K = b y_{1} b^{- 1}$

Com se sap que $a b = b a$ , llavors:

$K = a y_{2} a^{- 1} = a (b x b^{- 1}) a^{- 1} = b (a x a^{- 1}) b^{- 1} = b y_{1} b^{- 1}$

Obtenint Alice i Bob la mateixa trena.

Protocol de clau pública

Usant l'establiment de clau anterior, ara es pren una funció hash $H : B_{l + r}$ → { $0, 1$ } $^{k}$ que s'adapte del grup de trenes al mensage que es vol encriptar.

Generació de clau:
- Es tria un $x$ Є $B_{l + r}$ suficientment complicat
- Es tria una $a$ Є $L B_{l}$
- Es definix la clau pública com $(x, y)$ , a on $y = a x a^{- 1}$ , i la clau privada seria $a$

Encriptación: Prenent el mensage m Є {0,1}k i la clau pública definida
- Es tria una trena qualsevol $b$ Є $R B_{r}$
- Obtenint aixina el text sifrat $(c, d)$ , a on $c = b x b^{- 1}$ i $d = H (b x b^{- 1}) * m$

Dessifrat:
- En el text sifrat i la clau privada es calcula $m = H (a c a^{- 1}) * d$

Com $a$ i $b$ commuten, llavors $a c a^{- 1} = a b x b^{- 1} a^{- 1} = b a x a^{- 1} b^{- 1} = b y b^{- 1}$ . Aixina que $H (a x a^{- 1}) * d = H (b x b^{- 1}) * H (a x a^{- 1}) * m$ recuperant aixina el mensage original. Per a este protocol deu elegir-se un $x$ lo suficientment complicat per a evitar la “factorisació” de $x$ en $x_{1} x_{2} z$ , a on $x_{1}$ Є $L B_{l}$ , $x_{2}$ Є $R B_{r}$ i $z$ és una trena d'orde $l + r$ conmutable en $L B_{l}$ i $R B_{r}$ . Açò és aixina ya que si és possible descompondre fàcilment $x$ , llavors:

$b y b^{- 1} = (a x_{1} a^{- 1}) (b x_{2} b^{- 1}) z$ seria fàcil de calcular usant $y_{1} = (a x_{1} a^{- 1}) x_{2} z$ i $y_{2} = x_{1} (b x_{2} b^{- 1}) z$ sense conéixer $a$ o $b$ .^[1]

Referències

↑ «Pairing-Based One-Round Tripartite Key Agreement Protocols».Pairing-Based One-Round Tripartite Key Agreement Protocols.Consultat el 13 de juliol de 2019.

Bibliografia

I. Anshel and M. Anshel, From the Post-Markov theorem through decision problems to public-key cryptography, Amer. Math. Monthly 100 (1993), no. 9, 835–844.
I. Anshel, M. Anshel and D. Goldfeld, An algebraic method for public-key cryptography, Mathematical Research Letters 6 (1999) 287–291

E. Artin, Theory of braids, Annals of Math. 48 (1947), 101–126

Referències

Este artícul conté una traducció derivada de «Protocolo de Ko-Lee-Cheon-Hang-Park» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] «Pairing-Based One-Round Tripartite Key Agreement Protocols».Pairing-Based One-Round Tripartite Key Agreement Protocols.Consultat el 13 de juliol de 2019.

[1]