| La cifra la Ale-gamalja |
|
|
|
La idea general del método |
|
|
La idea ElGamal básica es que no existe los métodos eficaces de la decisión de la comparación ax == b (mod p)
Designaciones. A través de Z (n) designaremos las deducciones por el módulo n, a través de Z * (n) - el grupo multiplicativo de los elementos convertibles en Z (n). A través de ab (mod n) designaremos la edificación a en el grado b en el anillo Z (n). Hапомню que si p - el número simple, el grupo Z * (p) es isomorfo Z (p-1).
Que el número p y 2p+1 - simple, p> 2, v y w - que forman los grupos Z multiplicativos * (p) y Z * (2p+1) respectivamente.
El lema. Si v - que forma Z * (p), v0 = (p + (p+1) v) (mod 2p) - que forma multiplicativo los grupos Z * (2p). (Este grupo, es evidente, es isomorfo Z * (p)).
Los números p, 2p+1, v, v0, w se fijan en la elección del algoritmo.
|
Las consignas |
|
|
СЕКРЕТHЫЙ la consigna - el número x de Z * (p).
La consigna ABIERTA (y) es calculada en dos pasos.
- Encontramos primero z=v0x (mod 2p), z pertenece al grupo Z * (2p).
- Hаконец es calculada la consigna misma abierta y = wz (mod 2p+1), y pertenece al grupo Z * (2p+1).
El teorema. En cualquier elección de la consigna secreta (x) la consigna abierta (y) será el grupo Z multiplicativo que forma * (2p+1). Con otras palabras, la comparación ya = b (mod 2p+1) es soluble relativamente a a cualquiera b.
La prueba. El número w^z será el grupo Z que forma * (2p+1) iff los números z y 2p son simples. Hо z = v0x (mod 2p), donde v0 - que forma los grupos Z * (2p).
|
La firma electrónica |
|
|
Que s - el número (información), a que es necesario encontrar la firma electrónica, s pertenece al grupo Z (2p). Es escogido Para esto el número casual r del grupo Z * (2p), isomorfo Z * (p), y en calidad de la firma damos un par de los números (a, b), donde
a = a (r, s) = z-1*r*s = v0 (-x) *r*s (mod 2p); b = b (r, s) = wr (mod 2p+1). Puesto que
Z * (2p) = Z * (p) +Z * (2) = Z * (p) = Z (p-1), Esto
1/z = z-1 = v0-x = v0 (p-1-x). Así, la composición de la firma tiene que saber la consigna secreta (x), hablando más exactamente z=v0x.
Para la comprobación de la autenticidad de la firma es posible aprovecharse de la igualdad
ya = bs (mod 2p+1). Realmente,
ya = (wz) ^ (z-1*r*s) = w ^ (z*z-1*r*s) = wrs = (wr) ^s = bs (mod 2p+1) Por consiguiente, para la comprobación de la autenticidad de la firma basta de saber solamente la consigna abierta (y).
Al cálculo de la firma el número s (el fichero) se encuentra por medio de la hesh-función de misma dirección (el análogo MD4, pero otro).
|
Así: |
|
|
Designaciones.
p, 2p+1 - los números simples,
v, w - que forman los grupos Z * (p) y Z * (2p+1) соответсвенно,
v0 = p + (p+1) v - que forma Z * (2p),
x - la consigna secreta, el número de Z (p-1),
z - la expresión intermedia de Z (2p),
y - las aperturas la consigna, el número de Z * (2p+1),
s - el número informativo,
r - el número casual de Z (2p),
(a, b) - la firma electrónica,
a de Z (2p),
b de Z * (2p+1),
(c, d) - el mensaje cifrado, c de Z * (2p+1),
d de Z * (2p+1),
e - la expresión intermedia de Z * (2p+1). Hахождение de la llave abierta por secreto. x => y
- v0 = p + (p+1) *v (mod 2p)
- z = v0x (mod 2p)
- y = wz (mod 2p+1)
La firma electrónica x, s, r => a, b (r - casual)
- v0 = p + (p+1) *v (mod 2p)
- a = v0 (p-1-x) *r*s (mod 2p)
- b = ws (mod 2p+1)
La comprobación de la firma y, s, a, b => y/n
- ya == bs (mod 2p+1)
La cifración y, s, r => c, d
- e = yr (mod 2p+1)
- c = wr (mod 2p+1)
- d = s*e (mod 2p+1)
El desciframiento x, c, d => s
- v0 = p + (p+1) *v (mod 2p)
- z = v0x (mod 2p)
- 1/e = c2p-z (mod 2p+1)
- s = d/e (mod 2p+1)
|
|
|