#import "@preview/algo:0.3.2": algo, i, d, comment, code

#set page(
	numbering: "1 / 1",
	header: [
		#set text(8pt)
		_IFT436, Devoir 1 #h(1fr) Paulin Violette, 2023_
	],
)

#let code = rect.with(
  inset: 8pt,
  fill: rgb("e4e5fa"),
  width: 100%,
  radius: 6pt
  )

#let title(content) = {
	pagebreak(weak:true)
	set text(size:15pt)
	set align(center)
	v(10pt)
	[#content]
	v(10pt)
}

#title[= Devoir 1]

#line(length: 100%) 

#v(70pt)

#line(length: 100%)

#set par(
  first-line-indent: 1em,
  justify: true,
)
= Notes
Le code présenté est retrouvable sur #link("ssh://sherbrooke@bigblase.xyz:/srv/git/crypto2")\
mot de passe : `FDS8EbKiDNoJh2QN`\
Le code a été testé sous linux, kernel 6.5 et librairie à jour (sept 2023), en
utilisant gcc 13.2.1. 
Pour compiler, il faut d'abord créer le dossier _build_ à la racine du projet.
Pour tester, il faut faire ```sh make run part=<PART_NUMBER> eve=<ARGS_EVE>```.
Il _devrait_ être portable (C99, POSIX compliant)
#set heading(numbering: "I) a) i)")

= Diffie Hellman
On implémente les fonctions demandées. Ceci nous donne : 
#code[```c
#define MOD2POW63(n) ((n) % UINT64_MAX)

static inline uint32_t
gen()
{
	/* rand is between 0 and UINT32_MAX - 1 / 2 (because sign) */
	return rand() + rand() + (rand() % 1);
}
```

```c
int
main(int argc, char *argv[])
{
	srand(time(0)); /* init rand */

	uint32_t key_alice  = gen();
	uint32_t key_bob    = gen();

	uint64_t h_a = MOD2POW63(ipow(3, key_alice));
	uint64_t h_b = MOD2POW63(ipow(3, key_bob));

	printf("Alice generated key %d, sent h_a=%lu\n", key_alice, h_a);
	printf("Bob generated key %d, sent h_b=%lu\n",   key_bob,   h_b);


#ifdef EVE_INTERCEPT
	printf("Eve intercepted h_b and h_a.\n");

	uint32_t key_eve = gen();
	uint64_t h_e = MOD2POW63(ipow(3, key_eve));

	printf("Eve generated key %d. She sends h_a to Bob, and h_b to Alice.\n",
			key_eve);

	uint64_t k_e_a = MOD2POW63(ipow(h_a, key_eve));
	uint64_t k_e_b = MOD2POW63(ipow(h_b, key_eve));

	printf("Eve comptued k_e_a=%lu, k_e_b=%lu\n", k_e_a, k_e_b);
	printf("Eve sends h_e to Bob and Alice\n");

	h_a = h_e;
	h_b = h_e;
#endif

	uint64_t k_a = MOD2POW63(ipow(h_b, key_alice));
	uint64_t k_b = MOD2POW63(ipow(h_a, key_bob));

	printf("Alice computed k_a=%lu\n", k_a);
	printf("Bob computed k_b=%lu\n",   k_b);
...
  return 0;

}

```]

Pour pouvoir avoir une exponentiation rapide sur les entier, je l'ai 
#strike[trouvée sur stackoverflow] implémentée. Je laisse aussi
l'exponentiation modulaire qui sera utile pour la partie 2: 
#code[
```c
/* https://stackoverflow.com/a/101613/13156585 */
static uint64_t
ipow(uint32_t base, uint32_t exp)
{
    int result = 1;
    for (;;)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        if (!exp)
            break;
        base *= base;
    }

    return result;
}

static uint64_t
ipow_mod(uint32_t base, uint32_t exponent, uint32_t mod) {
  uint64_t x = 1;
  uint64_t y = base;

  while (exponent > 0) {
    if (exponent % 2 == 1)
      x = (x * y) % mod;
    y = (y * y) % mod;
    exponent = exponent / 2;
  }

  return (x % mod);
}
```]
== 
On a ici $(Pi_(A)^i, Pi_(B)^i) = "DHKEP" ; i=32$

== 
On fait tourner une fois sans qu'Eve n'intervienne.
#code[`Alice generated key -1792100893, sent h_a=18446744073108443291
Bob generated key -1044643954, sent h_b=18446744072800391545
Alice computed k_a=1639053353
Bob computed k_b=1639053353
Bob and Alice key match
`]

Eve voit passer $h_b$ et $h_a$.

Cette fois, Eve intervient, et intercepte $h_b$ et $h_a$ (ils ne seront donc 
pas déliverés).

On obtient :
#code[`Alice generated key -2077545126, sent h_a=2145716457
Bob generated key 1787548291, sent h_b=18446744071694128667
Eve intercepted h_b and h_a.
Eve generated key -1461028833. She sends h_a to Bob, and h_b to Alice.
Eve comptued k_e_a=18446744073569067097, k_e_b=18446744073273089683
Eve sends h_e_b to Bob and h_e_a to Alice
Alice computed k_a=18446744073569067097
Bob computed k_b=18446744073273089683
Bob and Alice keys match with Eve's!
`]

On note qu'a chaque envoie d'Alice ou Bob, Eve reçoit les messages, et choisis
ou non de les faires passer, et chaque message qu'Alice ou Bob reçoivent 
provient donc de Eve.

==
Alice et Bob ne voit aucune différence, si ce n'est un temps entre les 
messages plus important. En dehors de cela, il n'y veront aucune différence.

==
On voit pourtant que $k_b != k_a$ quand Eve manipule les hash. Cependant, 
comme Alice et Bob ne partagent pas leurs clef privées, il ne le verront pas.

= Chiffrement RSA
C'est les mêmes nombres que dans l'exercice de la semaine dernière. On a donc:

$N = 143, p = 11, q = 13, e = 7, d = 103$
== 
#code[```c
static uint32_t
E1(char message, uint32_t key_priv, uint32_t n){
	return ipow_mod(message, key_priv, n);
}

static uint32_t
D1(char cypher, uint32_t key_pub, uint32_t n){
	return ipow_mod(cypher, key_pub, n);
}
```]

Pour tester, j'ai il faudra aussi passer la valeur du message au moment 
d'exécuter le programme:`make run part=2 m=5`.

Lignes utils : #code[```c
int
main(int argc, char *argv[])
{
...
    uint32_t e1 = E1(atoi(argv[1]), e, n);
    uint32_t d1 = D1(e1,	    d, n);

    printf("m: %d, cypher: %u, decrypt: %u\n", atoi(argv[1]), e1, d1);

    return 0;
}
```]

On obtient : 

#table(
  columns: (1fr, 1fr, 1fr),
  inset: 10pt,
  align: center,
  [`m: 3, cypher: 42, decrypt: 3`],
  [`m: 5, cypher: 47, decrypt: 5`],
  [`m: 7, cypher: 6,  decrypt: 7`]
)

On remarque qu'à chaque fois, on a bien $m = d$, ce qui montre que le message 
d'origine est bien celui déchiffré.

La clef privée est le couple $(d, N)$, la clef publique le couple $(e, N)$.

Ainsi, Alice dispose de $(d, e, N)$, et Bob de $(d, N)$. Alice connait aussi
$p, q$ permettant de générer $N$.

Si Alice transmet la clef privée "Willy Nilly" à Bob, 
alors Eve peut intercepter $(N, d)$. Ainsi, elle pourrait 
déchiffrer les messages de Alice chiffré par cette clef, tout comme Bob. 

==
#table(
  columns: (1fr, 1fr),
  inset: 10pt,
  align: center,
  [`m: 0, cypher: 0, decrypt: 0`],
  [`m: 1, cypher: 1, decrypt: 1`]
)

On remarque que $forall x in bb(N)^* 0^x eq.triple 0 [N]$, et que 
$forall x in bb(N)^* 1^x eq.triple 1 [N]$. Pas de surprise dans le résultat.

Eve peut donc deviner le message pour $m=0, m=1$, même sans connaitre les clefs.

== Signatures RSA
On fait comme avant, mais on utilise la clef privée pour signer, et la clef 
publique pour vérifier.

On fait alors les fonctions suivantes : 
#code[```c
inline static uint32_t
Sign2(char message, uint32_t key_priv, uint32_t n){
	return E1(message, key_priv, n);
}

inline static uint32_t
Verif2(char signature, uint32_t key_pub, uint32_t n){
	return D1(signature, key_pub, n);
}
```]
#highlight(fill:rgb("e4e5ea"))[Notes : en `inline`-ant la fonction, on ne fait aucun appel supplémentaire,
on peut le voir comme un alias aux fonctions précédentes :)]

Si le message était plus compliqué, (ex : string) on pourrait alors faire 
la signature sur le hash du message. On le fait pas ici.
#table(
  columns: (1fr, 1fr, 1fr),
  inset: 10pt,
  align: center,
  [`m: 3, sign: 16, verif: 3`],
  [`m: 5, sign: 125, verif: 5`],
  [`m: 7, sign: 123, verif: 7`]
)

Où $italic("sk") = (d, N) = (103, 143), italic("pk") = (e, N) = (7, 143)$

Eve voit passer _pk_, le message et la signature.
Elle peut donc vérifier l'origine du message, mais ne peut pas reproduire de
message avec une signature qui serait cohérente avec ses clef.

Elle pourrait essayer de recomposer une clef privée qui convient.
Elle connait $N$. Il faut qu'elle trouve une décomposition de $N$ en nombre
premiers, avec seuelement deux composantes premières.
Or, une décomposition en nombre premier est en temps #link("https://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity")[#text(blue)[#underline[subexponentiel]]],
et non polynomial.

Eve ne peut donc pas reconstruire de clef privée pour resigner un message.
Elle devra utiliser une autre stratégie. Par exemple, elle pourrait essayer 
de regenerer une clef publique chez Bob dont elle maitrise la clef publique.