GNU Privacy Guard and You (Math Version)

This talk highlights why GPG is more relevant than ever in a modern age where government spying is the norm and no one on the internet can be trusted. We also take a dive in to how the RSA public key algorithm works at its core and how you can get started with GPG *today*.

Transcript

1. GNU Privacy Guard and you
2. ariejan https://ariejan.net
3. KABISA http://kabisa.nl
5. WHY is this YOUR problem?
6. “Just because you're paranoid doesn't mean they aren't after you” Joseph Heller, Catch-22
11. TRUST
12. HOW DOES IT WORK
13. HISTORY
14. SYMMETRIC KEY ENCRYPTION
16. Symmetric Key Encryption » Convert the clear alphabet into a cipher alphabet. » A simple symmetric encryption key: a b c d e f g h i j k l m n o p q r s t u v w x y z | | | | | | | | | | | | | | | | | | | | | | | | | | c d e f g h i j k l m n o p q r s t u v w x y z a b "a secret massage".encrypt # => "c ugetgv ocuucig"
17. Symmetric Key Decryption » Convert the cipher alphabet into a clear alphabet. » Decryption uses the same key, but in reverse. c d e f g h i j k l m n o p q r s t u v w x y z a b | | | | | | | | | | | | | | | | | | | | | | | | | | a b c d e f g h i j k l m n o p q r s t u v w x y z "c ugetgv ocuucig".decrypt # => "a secret massage"
18. ROT13 a b c d e f g h i j k l m n o p q r s t u v w x y z | | | | | | | | | | | | | | | | | | | | | | | | | | n o p q r s t u v w x y z a b c d e f g h i j k l m
19. ROT13 a b c d e f g h i j k l m n o p q r s t u v w x y z | | | | | | | | | | | | | | | | | | | | | | | | | | n o p q r s t u v w x y z a b c d e f g h i j k l m "Hello World".rot13.rot13.rot13.rot13 #=> "Hello World"
20. PUBLIC KEY ENCRYPTION
21. MATH
22. Modulo 21 % 7 # => 0 23 % 7 # => 2
23. Mod-7 [0, 1, 2, 3, 4, 5, 6]
24. Greatest Common Divisor a = 10; b = 4 a.gcd(b) # => 2
25. Multiplicative Inverse x * x⁻1 = 1
26. Multiplicative Inverse 3 * x⁻1 = 1 mod 11
27. Now for the INTERESTING stuff
28. GCD(4, 9) = 1
29. 4 * x⁻1 = 1 % 9
30. 4 * 7 = 28 = 1 % 9
31. ϕ
32. Euler's Totient
33. For any prime number p every number from 1 up to p − 1 has a GCD of 1 with p.
34. ϕ(p) = p - 1
35. RSA
36. Rivest Shamir Adleman
37. 1. Key Generation 2. RSA Function Evaluation
38. » Large Prime Number Generation » Calculate Modulus » Pick a Public Key » Calculate Private Key
39. Large Prime Number Generation
40. p = 11 q = 13
41. Calculate Modulus n = pq
42. p = 11 q = 13 n = p * q # => 143
43. Pick a Primary Key [3..ϕ(n))
44. Pick a Primary Key [3..ϕ(n)) ϕ(n)
45. Pick a Primary Key [3..ϕ(n)) ϕ(n) ϕ(p * q)
46. Pick a Primary Key [3..ϕ(n)) ϕ(n) ϕ(p * q) ϕ(p) * ϕ(q)
47. Pick a Primary Key [3..ϕ(n)) ϕ(n) ϕ(p * q) ϕ(p) * ϕ(q) p-1 * q-1
48. p = 11 q = 13 n = p * q # 143 phi = p-1 * q-1 # 120
49. p = 11 q = 13 n = p * q # 143 phi = p-1 * q-1 # 120 e = 7 # Picked from [3..phi] public_key = [e, n] # [7, 143]
50. Generate a Private Key
51. Generate a Private Key “Given two integers have GCD of 1, then the smaller nummer has a multiplicative inverse in the larger mod-space.”
52. Generate a Private Key “Given two integers have GCD of 1, then the smaller nummer has a multiplicative inverse in the larger mod-space.” GCD(7, 120) = 1
53. x * x⁻1 = 1 mod y
54. e * d = 1 mod phi
55. e * d = 1 mod phi 7 * d = 1 mod 120
56. p = 11 q = 13 n = p * q # 143 phi = p-1 * q-1 # 120 e = 7 # Picked from [3..phi] public_key = [e, n] # [7, 143] d = extended_euclid(e, phi) private_key = [d, n] # [103, 143]
57. RSA Key Pair public_key = [7, 143] private_key = [103, 143]
58. RSA Functions def encrypt(message, e, n) (message ** e) % n end def decrypt(message, d, n) (message ** d) % n end
59. Encrypt all the things encrypt(42, 7, 143) # (42 ** 7) % 143 #=> 81
60. Decryption is easy as well decrypt(81, 103, 143) # (81 ** 103) %143 #=> 42
61. Signing messages 1.Create a hash value of the message 2.Encrypt the hash value with your private key
62. Verifying messages 1.Create a hash value of the message 2.Decrypt the signature with their public key 3.Compare your and their hash values
63. WHY does RSA WORK?
64. Why does RSA work e*d = 1 mod ϕ(n)
65. LARGE numbers
66. » 2048 bit => 617 digit primes » 4096 bit => 1234 digit primes » 8192 bit => 2467 digit primes
67. NOW WHAT?!
68. » Get GPGTools for Mac » Sign your outgoing email » Create a Web of Trust
69. » Get GPGTools for Mac » Sign your outgoing email » Create a Web of Trust » Key Signing Party » Q&A Session
70. THANKS! » https://ariejan.net » ariejan@ariejan.net » @ariejan GPG Public Key » http://aj.gs/pubkey 8450 D928 4373 164E 25CC 7E0D AD73 9154 F713 697B