Cript

GUIÓN DE CRIPTOGRAFÍA
FUNCIONES DE UN SOLO SENTIDO

Ejercicio 1. Sea (a 1 , . . . , a k ) una secuencia super-creciente de números positivos (la suma de los términos
que preceden a a i es menorque a i , para todo i ). Elige n > a i , y u un entero positivo tal que gcd(n, u) =
∗
∗
∗
o
1. Define a i = ua i m´ d n. La función mochila (knapsack) asociada a (a 1 , . . . , a k ) es
f : Zk →N, f (x 1 , . . . , x k ) =
2

k
i =1

∗
xi ai .

∗
∗
Implementa esta función y su inversa, tal y como se explica en [2, §4.5]. La llave pública es (a 1 , . . . , a k ),
mientras que laprivada (y puerta de atrás) es ((a 1 , . . . , a k ), n, u).

Ejercicio 2. Sea p un (pseudo-)primo mayor o igual que vuestro número de identidad. Encuentra un
elemento primitivo, α, de Z∗ (se puedeusar [3, 2.132 (iv)]; para facilitar el criterio, es bueno escoger p de
p
forma que (p − 1)/2 sea también primo, y para ello usamos Miller-Rabin). Definimos
f : Zp → Zp , x → αx .
Calcula el inversode tu fecha de nacimiento con el formato AAAAMMDD.
Ejercicio 3. Escribe una función que, dado un entero a y un primo p con

a
p

= 1, devuelve r tal que

2

r ≡ a m´ d p ([1, §2.3.4];primero te hará falta implementar el símbolo de Jacobi [3, 2.149]).
o
En lo que sigue, p y q son enteros primos, y n = pq.
Ejercicio 4.
Sea a un entero que es residuo cuadrático módulo p y q. Usa elterema chino de los restos para
calcular todas las raíces cuadradas de a mod n from the square roots of a módulo p y q.
Sean a y b enteros tales que b 2 ≡ a m´ d n. Escribe una función que toma comoargumentos p, q
o
y b, y devuelve todas las raíces de a en Zn .
Ejercicio 5. Sea f : Zn → Zn la función de Rabin: f (x) = x 2 . Sea n = 48478872564493742276963. Sabemos que f (12) = 144 = f(37659670402359614687722). Usando esta información, calcula p y q (mira la
demostración de [1, Lemma 2.43]).
Ejercicio 6. Elige a 0 y a 1 dos cuadrados arbitrarios módulo n (n como en el Ejercicio 5). Sea...