# Crittografia RSA subtask 3-4-5

**URL:** <https://forum.olinfo.it/t/crittografia-rsa-subtask-3-4-5/6478>\
**Category:** Aiuto\
**Created:** [25 Dicembre 2020, 12:03am UTC](https://forum.olinfo.it/t/crittografia-rsa-subtask-3-4-5/6478 "2020-12-25T00:03:29Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![lollo36912](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/cab0a1/32.png) [@lollo36912](https://forum.olinfo.it/u/lollo36912)\
**Post date:** [25 Dicembre 2020, 12:03am UTC](https://forum.olinfo.it/t/crittografia-rsa-subtask-3-4-5/6478/1 "2020-12-25T00:03:30Z")

</div>

Stavo provando a risolvere “crittografia RSA” ma mi riconosce come output corretto solo le prime 2 subtask, alle altre da errore. Non riesco a capire dove ho sbagliato.

```auto
    #include <iostream>
        #include <cmath>

        using namespace std;

        void decifra(int N, int d, int L, int messaggio[], char plaintext[])
        {
        	long long int c=0,i=0;
        	for (i=0; i<L;i++)
        	{
        		c=messaggio[i];
        		c=pow(c,d);
        		c=c%N;
        		plaintext[i]=c;
        	}
        	plaintext[L]= '\0';
        	cout<<endl;
        	i=0;
        	while(i<=L)
        	{
        		cout<<plaintext[i]<<" ";
        		i++;
        	}
        }

```

---

<div class="post-metadata">

**Author:** ![mauro\_losmauro](https://forum.olinfo.it/user_avatar/forum.olinfo.it/mauro_losmauro/32/2910_2.png) [@mauro\_losmauro](https://forum.olinfo.it/u/mauro_losmauro)\
**Post date:** [25 Dicembre 2020, 8:36pm UTC](https://forum.olinfo.it/t/crittografia-rsa-subtask-3-4-5/6478/2 "2020-12-25T20:36:08Z")

</div>

Salve, prima di tutto buon natale 😄.  
Dati i valori di “c” e “d”, secondo le Assunzioni del problema, l’espressione c^d raggiunge valori che il long long int non può contenere (nessun tipo primitivo del c++ può contenere questi valori) quell’istruzione pow va in overflow

---

<div class="post-metadata">

**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\
**Post date:** [26 Dicembre 2020, 1:11pm UTC](https://forum.olinfo.it/t/crittografia-rsa-subtask-3-4-5/6478/3 "2020-12-26T13:11:54Z")

</div>

> [@lollo36912](#):
>
> ```auto
> while(i<=L)
> {
> cout<<plaintext[i]<<" ";
> i++;
> }
> 
> ```

In teoria non dovresti interagire con l’input e output essedo un esercizio con grader.

> [@mauro\_losmauro](#):
>
> Dati i valori di “c” e “d”, secondo le Assunzioni del problema, l’espressione c^d raggiunge valori che il long long int non può contenere

Giusto.

---

<div class="post-metadata">

**Author:** ![lollo36912](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/cab0a1/32.png) [@lollo36912](https://forum.olinfo.it/u/lollo36912)\
**Post date:** [28 Dicembre 2020, 10:25am UTC](https://forum.olinfo.it/t/crittografia-rsa-subtask-3-4-5/6478/4 "2020-12-28T10:25:11Z")

</div>

Innanzi tutto grazie per gli auguri 😃.  
Non avevo pensato a questo possibile problema, comunque ho provato a risolvere utilizzano i suggerimenti presenti nel testo del problema: (A · B) mod M = (A mod M · B mod M) mod M;  
Di conseguenza ho cambiato la parte di decifrazione del messaggio da:

```
for (i=0; i<L;i++)
        	{
        		c=messaggio[i];
        		c=pow(c,d);
        		c=c%N;
        		plaintext[i]=c;
        	}

```

a questo:

```
for (i=0; i<L;i++)
	{
		c=messaggio[i];
		if(d%2==0){
			A=d/2;
			B=A;
		} else {
			A=d/2;
			B=A+1;
		}
		A=pow(c,A);
		B=pow(c,B);
		A=A%N;
		B=B%N;
		c=(A*B)%N;
		plaintext[i]=c;
	}

```

in questo modo ho praticamente dimezzato le dimensioni dei valori, comunque mi continua a dare errore alle stesse subtask, potrei ripetere questo procedimento per suddividere ulteriormente ogni potenza, ma non credo sia la soluzione giusta.

---

<div class="post-metadata">

**Author:** ![mauro\_losmauro](https://forum.olinfo.it/user_avatar/forum.olinfo.it/mauro_losmauro/32/2910_2.png) [@mauro\_losmauro](https://forum.olinfo.it/u/mauro_losmauro)\
**Post date:** [28 Dicembre 2020, 10:34am UTC](https://forum.olinfo.it/t/crittografia-rsa-subtask-3-4-5/6478/5 "2020-12-28T10:34:57Z")

</div>

Dividere in due non basta, se ti viene dato per esempio d = 100 e c =2, hai diviso il calcolo in 2^(99) \* 2^(99) e considerando che nel long long int il massimo valore è tipo 2^(63) , siamo ancora fuori con i valori 😅

---

<div class="post-metadata">

**Author:** ![mauro\_losmauro](https://forum.olinfo.it/user_avatar/forum.olinfo.it/mauro_losmauro/32/2910_2.png) [@mauro\_losmauro](https://forum.olinfo.it/u/mauro_losmauro)\
**Post date:** [28 Dicembre 2020, 11:25am UTC](https://forum.olinfo.it/t/crittografia-rsa-subtask-3-4-5/6478/6 "2020-12-28T11:25:58Z")

</div>

Comunque per questo problema si può fare 60/100 facendo la potenza in O(esponente) , cioè l’algoritmo basilare, per fare 100/100 bisogna fare solo log2(esponente) moltiplicazioni per ogni numero

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [28 Dicembre 2020, 12:46pm UTC](https://forum.olinfo.it/t/crittografia-rsa-subtask-3-4-5/6478/7 "2020-12-28T12:46:50Z")

</div>

L’algoritmo per farlo è molto noto e non è nemmeno troppo costruttivo ragionarci invece che impararlo, quindi è più funzionale spiegarlo direttamente.  
Puoi farlo principalmente in 2 modi:

### Metodo 1:

Stai cercando di calcolare a^b puoi sfruttare il fatto che a^b=a^{\lceil b/2 \rceil} \* a^{\lfloor b/2 \rfloor} considerando che a^{\lceil b/2 \rceil} = a^{\lfloor b/2 \rfloor} per b pari e a^{\lceil b/2 \rceil} = a^{\lfloor b/2 \rfloor} \* b per b dispari puoi notare come per ottenere a^b basta a^{\lfloor b/2 \rfloor} ed avendo come casi base a^0 = 1, a^1 = a allora ti basteranno log\_2(b) chiamate per trovare a^b. Inoltre l’unica operazione utilizzata è la moltiplicazione che è compatibile con il modulo, infatti (a\*b) MOD x = ((a MOD x)\*(b MOD x)) MOD x

codice:

```auto
int fast_pow(int base, int esp, int MOD) {
	if(esp == 0)
		return 1;
	if(esp == 1)
		return base % MOD;
	long long half = fast_pow(base, esp / 2, MOD);
	long long ans = (half * half) % MOD;
	if(esp % 2)
		ans = (ans * base) % MOD;
	return ans;
}

```

### Metodo 2:

Consideriamo la rappresentazione in base 2 di b= d\_0\*2^0+d\_1\*2^1+d\_2\*2^2+...+d\_k\*2^k con d\_i = 0 o d\_i = 1 per ogni i. Allora quello che stiamo cercando di calcolare è a^{d\_0\*2^0+d\_1\*2^1+d\_2\*2^2+...+d\_k\*2^k} che corrisponde a a^{d\_0\*2^0}\*a^{d\_1\*2^1}\*a^{d\_2\*2^2}\*...\*a^{d\_k\*2^k} ed essendo i numeri rappresentati in binario nel calcolatore il calcolo diventa comodo infatti possiamo seguire il seguente procedimento:

- Iniziamo ponendo il risultato attuale r=1
- Calcoliamo a^{(2^0)} =a e sappiamo che se d\_0 = 1 allora dovremo moltiplicare r per a.
- Calcoliamo a^{(2^1)} = a^2 e sappiamo che se d\_1 = 1 allora dovremo moltiplicare r per a^2
- Calcoliamo a^{(2^2)} = a^4 e sappiamo che se d\_1 = 1 allora dovremo moltiplicare r per a^4
- Procediamo in questo modo fino a quando non terminano i bit del numero che stiamo considerando. Il codice che implementa il metodo 2 è molto semplice, e leggermente più veloce del metodo 1 in quanto è iterativo:  
codice:

```auto
int fast_pow(int base, int esp, int MOD){
	long long r = 1; // risultato
	long long pot_base = base; // a, a^2, a^4....
	while(esp > 0){
		if(esp % 2) // controllo l'ultimo bit (d_i)
			r = (r * pot_base) % MOD;
		pot_base = (pot_base * pot_base) % MOD; // elevo alla seconda
		esp >>= 1; // elimino l'ultimo bit
	}
	return r;
}

```