slides/src/rsa-and-homomorphicmultiplication/rsa-and-homomorphicmultiplication.md
src/rsa-and-homomorphicmultiplication/rsa-and-homomorphicmultiplication.mdRaw
1# RSA and Homomorphic Multiplication
2
3<img src="https://arnaucube.com/img/logoArnauCubeTransparent.png" style="max-width:20%; float:right;" />
4
5
6- https://arnaucube.com
7- https://github.com/arnaucube
8- https://twitter.com/arnaucube
9<br><br><br>
10<div style="float:right;font-size:80%;">
11 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/"><img src="https://licensebuttons.net/l/by-nc-sa/4.0/88x31.png" /></a>
12 <br>
13 2018-11-30
14</div>
15
16---
17
18- Intro
19- Public key cryptography
20- Basics of modular arithmetic
21- Brief history of RSA
22- Keys generation
23- Prime numbers
24- Encryption
25- Decryption
26- What's going on in encryption and decryption?
27- Signature
28- Verification of the signature
29- Homomorphic Multiplication with RSA
30- Resources
31
32---
33# Intro
34- I'm not an expert on the field, neither a mathematician. Just an engineer with interest for cryptography
35- Short talk (15 min), with the objective to make a practical introduction to the RSA cryptosystem
36- Is not a talk about mathematical demostrations, is a talk with the objective to get the basic notions to be able to do a practical implementation of the algorithm
37- After the talk, we will do a practical workshop to implement the concepts. We can offer support for Go, Rust, Python and Nodejs (you can choose any other language, but we will not be able to help)
38
39---
40# Public key cryptography
41
42
43---
44Some examples:
45- RSA
46- Paillier
47- ECC (Corba el·líptica)
48
49---
50# Basics of modular arithmetic
51- Modulus, `mod`, `%`
52- Remainder after division of two numbers
53
54
55
56```
575 mod 12 = 5
5814 mod 12 = 2
5983 mod 10 = 3
60```
61
62```
635 + 3 mod 6 = 8 mod 6 = 2
64```
65
66---
67
68# Brief history of RSA
69- RSA (Rivest–Shamir–Adleman): Ron Rivest, Adi Shamir, Leonard Adleman
70- year 1977
71- one of the first public key cryptosystems
72- based on the difficulty of factorization of the product of two big prime numbers
73
74---
75# Prime numbers
76- We need an asymmetric key, in a way where we can decrypt a message encrypted with the asymetric key
77- Without allowing to find the private key from the public key
78- in RSA we resolve this with factorization of prime numbers
79- using prime numbers for $p$ and $q$, it's difficult factorize $n$ to obtain $p$ and $q$, where $n=p*q$
80
81---
82
83Example:
84If we know $n$ which we need to find the $p$ and $q$ values where $p*q=n$:
85```
86n = 35
87```
88To obtain the possible factors, is needed to brute force trying different combinations, until we find:
89```
90p = 5
91q = 7
92```
93In this case is easy as it's a simple example with small numbers. The idea is to do this with big prime numbers
94
95---
96
97Another exmample with more bigger prime numbers:
98```
99n = 272604817800326282194810623604278579733
100```
101From $n$, I don't have a 'direct' way to obtain $p$ and $q$. I need to try by brute force the different values until finding a correct combination.
102```
103p = 17975460804519255043
104q = 15165386899666573831
105n = 17975460804519255043 * 15165386899666573831 = 272604817800326282194810623604278579733
106```
107
108---
109
110If we do this with non prime numbers:
111```
112n = 32
113We can factorize 32 = 2 * 2 * 2 * 2 * 2
114combining that values in two values X * Y
115for example (2*2*2) * (2*2) = 8*4 = 32
116we can also take 2 * (2*2*2*2) = 2 * 16 = 32
117...
118```
119
120---
121
122One example with bigger non prime numbers:
123```
124n = 272604817800326282227951471308464408608
125We can take:
126p = 17975460804519255044
127q = 15165386899666573832
128
129Or also:
130p = 2
131q = 136302408900163141113975735654232204304
132...
133```
134
135In the real world:
136- https://en.wikipedia.org/wiki/RSA_numbers
137- https://en.wikipedia.org/wiki/RSA_Factoring_Challenge#The_prizes_and_records
138
139So, we are basing this in the fact that is not easy to factorize big numbers composed by big primes.
140
141
142---
143# Keys generation
144- PubK: $e$, $n$
145- PrivK: $d$, $n$
146- are choosen randomly 2 big prime numbers $p$ and $q$, that will be secrets
147- $n = p * q$
148- $λ$ is the Carmichael function
149 - $λ(n) = (p − 1) * (q − 1)$
150- Choose a prime number $e$ that satisfies $1 < e < λ(n)$ and $gcd(e, λ(n))=1$
151 - Usually in examples is used $e = 2^16 + 1 = 65537$
152- $d$ such as $e * d = 1 mod λ(n)$
153 - $d = e^(-1) mod λ(n) = e modinv λ(n)$
154
155---
156
157### Example
158- `p = 3`
159- `q = 11`
160- `e = 7` value choosen between 1 and λ(n)=20, where λ(n) is not divisible by this value
161- `n = 3 * 11 = 33`
162- `λ(n) = (3-1) * (11-1) = 2 * 10 = 20`
163- `d` such as `7 * d = 1 mod 20`
164- `d = 3`
165- PubK: `e=7, n=33`
166- PrivK: `d=3, n=33`
167
168---
169
170### Naive code
171```python
172def egcd(a, b):
173 if a == 0:
174 return (b, 0, 1)
175 g, y, x = egcd(b%a,a)
176 return (g, x - (b//a) * y, y)
177
178def modinv(a, m):
179 g, x, y = egcd(a, m)
180 if g != 1:
181 raise Exception('No modular inverse')
182 return x%m
183```
184
185---
186
187```
188def newKeys():
189 p = number.getPrime(n_length)
190 q = number.getPrime(n_length)
191
192 # pubK e, n
193 e = 65537
194 n = p*q
195 pubK = PubK(e, n)
196
197 # privK d, n
198 phi = (p-1) * (q-1)
199 d = modinv(e, phi)
200 privK = PrivK(d, n)
201
202 return({'pubK': pubK, 'privK': privK})
203```
204
205---
206
207# Encryption
208- Brenna wants to send the message `m` to Alice, so, will use the Public Key from Alice to encrypt `m`
209- `m` powered at `e` of the public key from Alice
210- evaluate at modulus of `n`
211
212### Example
213- message to encrypt `m = 5`
214- receiver public key: `e=7, n=33`
215- `c = 5 ^ 7 mod 33 = 78125 mod 33 = 14`
216
217### Naive code
218```python
219def encrypt(pubK, m):
220 c = (m ** pubK.e) % pubK.n
221 return c
222```
223
224---
225# Decrypt
226- from an encrypted value `c`
227- `c` powered at `d` of the private key of the person to who the message was encrypted
228- evaluate at modulus of `n`
229
230### Example
231- receiver private key, PrivK: `d=3, n=33`
232- `m = 14 ^ 3 mod 33 = 2744 mod 33 = 5`
233
234### Naive code
235```python
236def decrypt(privK, c):
237 m_d = (c ** privK.d) % privK.n
238 return m_d
239```
240
241---
242# What's going on when encrypting and decrypting?
243
244
245
246---
247
248```
249n = pq
250e
251phi = (p-1)(q-1)
252d = e^-1 mod (phi) = e^-1 mod (p-1)(q-1)
253
254# encrypt
255c = m^e mod n = m^e mod pq
256
257# decrypt
258m' = c^d mod n = c ^(e^-1 mod (p-1)(q-1)) mod pq =
259 = (m^e)^(e^-1 mod (p-1)(q-1)) mod pq =
260 = m^(e * e^-1 mod (p-1)(q-1)) mod pq =
261 = m^(1 mod (p-1)(q-1)) mod pq =
262 [theorem in which we're not going into details]
263 a ^ (1 mod λ(N)) mod N = a mod N
264 [/theorem]
265 = m mod pq
266```
267
268
269---
270# Signature
271- encryption operation but using PrivK instead of PubK, and PubK instead of PrivK
272
273- having a message `m`
274- power of `m` at `d` of the private key from the signer person
275- evaluated at modulus `n`
276
277---
278
279### Example
280- private key of the person emitter of the signature: `d = 3, n = 33`
281- message to be signed: `m=5`
282- signature: `s = 5 ** 3 % 33 = 26`
283
284### Naive code
285```python
286def sign(privK, m):
287 s = (m ** privK.d) % privK.n
288 return s
289```
290
291---
292
293# Verification of the signature
294- having message `m` and the signature `s`
295- elevate `m` at `e` of the public key from the signer
296- evaluate at modulus of `n`
297
298---
299
300### Example
301- public key from the singer person `e=7, n=33`
302- message `m=5`
303- signature `s=26`
304- verification `v = 26**7 % 33 = 5`
305- check that we have recovered the message (that `m` is equivalent to `v`) `m = 5 = v = 5`
306
307### Naive code
308```python
309def verifySign(pubK, s, m):
310 v = (s ** pubK.e) % privK.n
311 return v==m
312```
313
314---
315
316# Homomorphic Multiplication
317- from two values $a$ and $b$
318- encrypted are $a_{encr}$ and $b_{encr}$
319- we can compute the multiplication of the two encrypted values, obtaining the result encrypted
320- the encrypted result from the multiplication is calculated doing: $c_{encr} = a_{encr} * b_{encr} mod n$
321- we can decrypt $c_{encr}$ and we will obtain $c$, equivalent to $a * b$
322
323- Why:
324```
325((a^e mod n) * (b^e mod n)) mod n =
326= (a^e * b^e mod n) mod n = (a*b)^e mod n
327```
328
329---
330
331### Example
332- PubK: `e=7, n=33`
333- PrivK: `d=3, n=33`
334- `a = 5`
335- `b = 8`
336- `a_encr = 5^7 mod 33 = 78125 mod 33 = 14`
337- `b_encr = 8^7 mod 33 = 2097152 mod 33 = 2`
338- `c_encr = (14 * 2) mod 33 = 28 mod 33 = 28`
339- `c = 28 ^ 3 mod 33 = 21952 mod 33 = 7`
340- `c = 7 = a * b % n = 5 * 8 % 33 = 7`, on `5*8 mod 33 = 7`
341- take a `n` enough big, if not the result will be cropped by the modulus
342
343---
344
345### Naive code
346```python
347def homomorphic_mul(pubK, a, b):
348 c = (a*b) % pubK.n
349 return c
350```
351
352---
353# Small demo
354[...]
355
356# And now... practical implementation
357- full night long
358- big ints are your friends