1
00:00:00,000 --> 00:00:04,300
So RSA. Now Alice chooses 
two large primes, p and q,

2
00:00:04,300 --> 00:00:08,700
and selects any integer, e, satisfying 1 is less 
than e is less than p minus 1 times q minus 1.

3
00:00:08,700 --> 00:00:12,633
So before it was just p minus 1, now we have 
the product p minus 1 times q minus 1,

4
00:00:12,633 --> 00:00:13,333


5
00:00:13,333 --> 00:00:16,266
and e is co-prime to p 
minus 1 and q minus 1.

6
00:00:16,266 --> 00:00:16,933


7
00:00:16,933 --> 00:00:19,133
So here's where the two
primes are coming in.

8
00:00:19,133 --> 00:00:20,333


9
00:00:20,333 --> 00:00:23,100
Alice then makes the
pair e and n public,

10
00:00:23,100 --> 00:00:27,366
so n is p times q. So she makes 
the product and e public,

11
00:00:27,366 --> 00:00:29,500
and computes her 
private key, d, satisfying

12
00:00:29,500 --> 00:00:32,400
1 is less than d is less than 
p minus 1 times q minus 1,

13
00:00:32,400 --> 00:00:35,833
and e d is congruent to 1 mod 
p minus 1 times q minus 1.

14
00:00:35,833 --> 00:00:38,600
Again, Alice can compute this 
quickly because she knows p,

15
00:00:38,600 --> 00:00:41,700
she knows q, so she knows p minus 
1 and q minus 1, and so she can

16
00:00:41,700 --> 00:00:44,633
compute the inverse of e very quickly 
using the Extended Euclidean Algorithm.

17
00:00:44,633 --> 00:00:45,633


18
00:00:45,633 --> 00:00:48,900
This is a key, key
fact. Alice knows p and q

19
00:00:48,900 --> 00:00:52,000
so she can compute p minus 
1 and q minus 1 quickly.

20
00:00:52,000 --> 00:00:54,000
Remember that sentence.

21
00:00:54,000 --> 00:00:55,200


22
00:00:55,200 --> 00:00:58,166
So what does Bob do? Well 
Bob sends his message.

23
00:00:58,166 --> 00:01:02,200
His message, M, is between 0 and 
n minus 1 or p q minus 1 inclusive.

24
00:01:02,200 --> 00:01:03,500


25
00:01:03,500 --> 00:01:06,300
Bob then computes a 
ciphertext, C, satisfying

26
00:01:06,300 --> 00:01:08,733
0 is less than equal 
to C is less than p q,

27
00:01:08,733 --> 00:01:10,633
and C is congruent 
to M to the e mod p q.

28
00:01:10,633 --> 00:01:14,533
So we're basically reducing m to the
e to the least non-negative residue.

29
00:01:14,533 --> 00:01:15,166


30
00:01:15,166 --> 00:01:17,933
And we're going to send C 
across the channel. So Eve knows

31
00:01:17,933 --> 00:01:20,000
e, n, and C.

32
00:01:20,000 --> 00:01:21,900


33
00:01:21,900 --> 00:01:24,633
Bob then sends C to Alice 
and Alice then computes

34
00:01:24,633 --> 00:01:27,200
R is congruent to C to the d mod p q.

35
00:01:27,200 --> 00:01:28,500


36
00:01:28,500 --> 00:01:31,433
Now just like before, we’d like 
to prove that R is equal to M.

37
00:01:31,433 --> 00:01:34,166
It's going to take a little 
bit of effort, but we can do it.

38
00:01:34,166 --> 00:01:38,433
But this is the scheme, okay? So it's 
basically just like the one prime situation

39
00:01:38,433 --> 00:01:39,233


40
00:01:39,233 --> 00:01:41,066
except we use two primes.

41
00:01:41,066 --> 00:01:41,733


42
00:01:41,733 --> 00:01:43,600
Let's take a look at the diagram.

43
00:01:43,600 --> 00:01:44,266


44
00:01:44,266 --> 00:01:48,266
So again, you can see the difference. 
Eve knows e and p q which is n.

45
00:01:48,266 --> 00:01:49,366


46
00:01:49,366 --> 00:01:52,000
Alice chooses the p and the q

47
00:01:52,000 --> 00:01:56,566
and chooses the e and 
computes the d satisfying

48
00:01:56,566 --> 00:01:59,633
d is the inverse of e mod p 
minus 1 times q minus 1.

49
00:01:59,633 --> 00:02:01,800
Bob takes his message, C - 

50
00:02:01,800 --> 00:02:05,166
Bob takes his message, M, and 
encrypts it using M to the e mod p q

51
00:02:05,166 --> 00:02:07,200
and sends C across 
the insecure channel,

52
00:02:07,200 --> 00:02:10,633
and Alice is trying to compute R 
is congruent to C the d mod p q. 

53
00:02:10,633 --> 00:02:14,633
So just like before, computing the 
e-th root of C is going to be difficult

54
00:02:14,633 --> 00:02:16,233
mod p q.

55
00:02:16,233 --> 00:02:19,833
Again something you can try on 
your own, but here's the main idea.

56
00:02:19,833 --> 00:02:20,466


57
00:02:20,466 --> 00:02:24,800
Let's see the proof of the major 
proposition here; R equals M.

58
00:02:24,800 --> 00:02:26,933


59
00:02:26,933 --> 00:02:29,066
What's the idea that we're going 
to use here? We're actually going to

60
00:02:29,066 --> 00:02:32,700
piggyback off of the exponentiation 
cipher proof from before.

61
00:02:32,700 --> 00:02:36,000
So step 1 is to reduce to that case twice, 

62
00:02:36,000 --> 00:02:38,666
and step 2 is to put that together.

63
00:02:38,666 --> 00:02:42,200
So since e d is congruent to 1
mod p minus 1 times q minus 1,

64
00:02:42,200 --> 00:02:45,766
Transitivity of Divisibility tells us that 
e d is congruent to 1 mod p minus 1,

65
00:02:45,766 --> 00:02:48,233
and e d is congruent 
to 1 mod q minus 1.

66
00:02:48,233 --> 00:02:49,333


67
00:02:49,333 --> 00:02:51,066
Since e d…

68
00:02:51,066 --> 00:02:52,500


69
00:02:52,500 --> 00:02:56,000
since the gcd of e d and p 
minus 1 and q minus 1 is 1,

70
00:02:56,000 --> 00:02:56,733


71
00:02:56,733 --> 00:02:58,600
GCD From

72
00:02:58,600 --> 00:03:01,733
Prime Factorization tells us that 
the gcd of e d and p minus 1 is 1,

73
00:03:01,733 --> 00:03:04,800
and the gcd of e d 
and q minus 1 is 1.

74
00:03:04,800 --> 00:03:08,300
In particular, we're really interested in the 
fact that the gcd of e and p minus 1 is 1,

75
00:03:08,300 --> 00:03:10,233
and the gcd of e and q minus 1 is 1,

76
00:03:10,233 --> 00:03:12,700
okay, but we get both so I 
might as well mention it.

77
00:03:12,700 --> 00:03:14,666


78
00:03:14,666 --> 00:03:17,566
So thus, as C is congruent 
to M to the e mod p q,

79
00:03:17,566 --> 00:03:21,400
Spitting the Modulus states that C 
is congruent to M to the e mod p,

80
00:03:21,400 --> 00:03:23,800
and C is congruent 
to M to the e mod q.

81
00:03:23,800 --> 00:03:24,833


82
00:03:24,833 --> 00:03:27,566
Similarly by Splitting the Modulus 
again, we have that R is congruent to

83
00:03:27,566 --> 00:03:31,133
C to the d mod p, and R is 
congruent to C to the d mod q.

84
00:03:31,133 --> 00:03:34,566
So now if we look at the situation, pretend 
you're dividing your screen in half

85
00:03:34,566 --> 00:03:36,933
along those “and” symbols, okay?

86
00:03:36,933 --> 00:03:39,633
If you look at the left hand 
side, you have everything

87
00:03:39,633 --> 00:03:42,466
mod p or mod p minus 1 that
we had in the previous theorem,

88
00:03:42,466 --> 00:03:44,366
and if you look at the other side 
we have everything mod q or

89
00:03:44,366 --> 00:03:46,500
q minus 1 that we had 
in the previous theorem.

90
00:03:46,500 --> 00:03:49,066
So if I apply that proposition 
twice, what am I going to get?

91
00:03:49,066 --> 00:03:51,166
I'm going to get that R is
congruent to M mod p,

92
00:03:51,166 --> 00:03:53,600
and R is congruent to M mod q.

93
00:03:53,600 --> 00:03:54,266


94
00:03:54,266 --> 00:03:57,033
So that was our goal here. We 
took the general situation of RSA,

95
00:03:57,033 --> 00:03:59,733
split it up into like two
single prime situations,

96
00:03:59,733 --> 00:04:02,766
and then brought them back by 
using the previous proposition.

97
00:04:02,766 --> 00:04:04,700


98
00:04:04,700 --> 00:04:08,266
We now did - we might have needed to 
reduce this a little bit more, but that's okay.

99
00:04:08,266 --> 00:04:10,900
I'm not going to get into 
small, small details like that.

100
00:04:10,900 --> 00:04:12,900
This is the big picture idea, okay?

101
00:04:12,900 --> 00:04:15,800
So now we have R is congruent to M 
mod p, and R is congruent to M mod q.

102
00:04:15,800 --> 00:04:18,300
We can put it together using

103
00:04:18,300 --> 00:04:19,133


104
00:04:19,133 --> 00:04:21,233
Splitting the Modulus or
Chinese Remainder Theorem.

105
00:04:21,233 --> 00:04:24,866
So you put them together, what do we get? 
We get that R is congruent to M mod p q,

106
00:04:24,866 --> 00:04:26,233


107
00:04:26,233 --> 00:04:28,566
but 0 is less than or equal to M is…

108
00:04:28,566 --> 00:04:30,900
0 is less than or equal to R 
and M which is less than p q

109
00:04:30,900 --> 00:04:34,033
and that shows us that R is equal to M, 

110
00:04:34,033 --> 00:04:34,833


111
00:04:34,833 --> 00:04:36,633
And that finishes the proof.

112
00:04:36,633 --> 00:04:37,500


113
00:04:37,500 --> 00:04:40,166
So that's the idea behind RSA. So RSA:

114
00:04:40,166 --> 00:04:44,466
exponentiation cipher with two primes. If 
you remember it like that, it might help you to

115
00:04:44,466 --> 00:04:46,499
remember this in practice.