Question

Need help understanding an encryption problem.

Answer 1

I'm not sure what the o with the line through it means.

Answer 2

That's the Euler \(\phi\)-function (phi-function). It's defined as\[\phi(n):=\#\{m\in\mathbb{N}|1\le m\le n\text{ and }\gcd(m,n)=1\}\]

Answer 3

from wikipedia The algorithm

Choose two distinct prime numbers, p and q.
Let n = pq.
Let φ(pq) = (p − 1)(q − 1). (φ is totient function).
Pick an integer e such that 1 < e < φ(pq), and e and φ(pq) share no divisors other than 1 (e and φ(pq) are coprime).
Find d which satisfies

.

d is a secret private key exponent.

The public key consists of e (often called public exponent) and n(often called modulus). The private key consists of e and d (private exponent).

The message m is encrypted using formula

where c is the encrypted message. The encrypted message is decrypted using formula

Encryption and decryption formulas show how to encode and decode a single integer. Bigger (or different) pieces of information are encoded by converting them into (potentially large) integers first. As RSA is not particularly fast, it is usually only to encrypts the key of some faster algorithm. After RSA decrypts the key, this supplementary algorithm uses it to decrypt the rest of the message.

RSA algorithm is fundamentally based on the Euler theorem:

where a and n are positive integers and a is a co-prime to n.

To break the algorithm from the mathematical side, one needs to solve the factoring problem (find the two prime numbers that, when multiplied, produce the given result). When the picked numbers are large enough, the problem cannot be easily solved by brute force and at least currently it also does not have easier analytic solution.

Answer 4

In case you aren't familiar with the notation I used, the # meant the size of the set.

Answer 5

The phi-function is fairly nice to use. For example, \[\phi(p^k)=p^k-p^{k-1}\]where \(p\) is prime, and \(k\) is a positive integer. Moreover, if \(m,n\) are two positive integers,\[\phi(mn)=\phi(m)\phi(n).\]Knowing those two things, you can easily calculate \(\phi(n)\) for any integer \(n\), assuming you know its prime factorization.

Answer 6

So for part (a)

o(7)o(11) I know that the only factors of 7 and 11 are 1

Answer 7

Since 7 and 11 are both prime, you can use the formula I provided above. So\[\phi(7\cdot11)=\phi(7)\phi(11)=(7^1-7^0)(11^1-11^0)=(7-1)(11-1)=6\cdot10=60\]

Answer 8

Ah, that makes sense. :)

So for part (b) the unique integer d satisfying 1 <= d <= o(n) and de.

would be 1 <= d <= 60 and d(23) 1 mod 60

Answer 9

correct.

Answer 10

1 mod 60 is just 1

but I'm still not sure how to solve for d

Answer 11

You haven't learned how to solve for inverses in modular multiplication?

Answer 12

no, don't thinks so

Answer 13

Hmm. That makes things rather difficult.

Answer 14

Well, in the class I am taking, my teacher just writes lots of complicated equations on the board that no one understands without really explaining them. So the students all have a very hard time with the the homework problems. But for the test we basically just memorize old test problems he gives us so I never really learn that much.

Answer 15

So basically if I figure out the homework I get good grades. lol

Answer 16

Alright, well the most elementary way to find the multiplicative inverses is by using the euclidean algorithm. You've learned about the euclidean algorithm right?

Answer 17

yeah

Answer 18

Excellent. So the first step is to write out the entire process. Since we want the inverse of 23 modulo 60, we'll be using 23 and 60 as the starting points in the euclidean algorithm.\[60=23*2+14\implies 14=60-23*2\]\[23=14*1+9\implies9=23-14*1\]\[14=9*1+5\implies5=14-9*1\]\[9=5*1+4\implies4=9-5*1\]\[5=4*1+1\implies1=5-4*1\]This is unfortunately a rather long example. But now, we just start substituting equations into each other.

Answer 19

So\[1=5-(9-5)=2*5-9\]\[2*5-9=2*(14-9)-9=2*14-3*9\]\[2*14-3*9=2*14-3*(23-14)=5*14-3*23\]\[5*14-3*23=5*(60-23*2)-3*23=5*60-13*23.\]Thus,\[1=5*60-13*23\]

Answer 20

Look through my work above, and make sure you can see how I got from each step to the next.

Answer 21

Yep, all looks good.

Answer 22

Thus, \(-13\equiv 47\pmod{60}\) is the multiplicative inverse of 23 modulo 60.

Answer 23

To convince yourself of that, you can take that final equation mod 60 to get\[1\equiv5*60\pmod{60}-13*23\pmod{60}\equiv-13*23\pmod{60}\]or check it on wolfram http://www.wolframalpha.com/input/?t=crmtb01&f=ob&i=23*47%20mod%2060

Answer 24

I don't understand where the 47 came from.

Answer 25

\(60-13=47\), so \(-13\equiv 47\pmod{60}\).

Answer 26

oh I see, makes sense now.

Answer 27

does d = 47 then?

Answer 28

Yes.

Answer 29

Wait, hold on.

Answer 30

Nevermind. Just panicked about nothing.

Answer 31

Ah ok, looks good. :)

so for part (c) would we need to find what e is?

Answer 32

We already know \(e=23\). We want to solve for \(m\).

Answer 33

ah right.

Answer 34

So I know that 1<=m<=60 and c = 25

Answer 35

I would need to solve for m in this equation? 25 m^23 mod 60

Answer 36

You need to look at it mod 77, and not mod 60, but yes. That is the equation where you want to solve for \(m\).

Fortunately, decrypting RSA is remarkably easy.

Answer 37

All you need to do, is find\[25^{47}\pmod{77}\]This looks intimidating, but is actually not that bad.

Do you want to know the reasoning behind why need to exponentiate c to the d-th power?

Answer 38

Sure

Answer 39

We start with\[c\equiv m^e\pmod{n}.\]Now we need to a theorem by Euler that says\[a^{\phi(n)}\equiv 1\pmod{n}\]for any positive integer \(n\), and any integer \(a\). Let \(d\) be the multiplicative inverse of \(e\) modulo \(\phi(n)\) (so \(de\equiv1\pmod{\phi(n)}\)). Now consider\[c^d\equiv(m^e)^d\pmod{n}\]\[c^d\equiv m^{ed}\pmod{n}\]But since \(ed\equiv1\pmod{\phi(n)}\), we get that\[c^d\equiv m^{1+\phi(n)}\pmod{n}\]\[c^d\equiv m\cdot m^{\phi(n)}\pmod{n}\]\[c^d\equiv m\cdot1\equiv m\pmod{n}.\]

Answer 40

ah cool, so that shows how you switched the equation from 25 m^23 mod 77 to 25^47 mod 77

Answer 41

Do you think I would need to show these steps in my homework?

Answer 42

I don't think you would need to provide a proof of RSA (which is what I just showed) on your homework. I suspect the process of reversing exponentiation was probably covered in class (or this problem would be much more difficult). But it always helps to have an understanding of why certain operations work the way they do.

Answer 43

makes sense

Answer 44

So going back to your problem, that just leaves us with \(25^{47}\pmod{77}\). Have you learned successive squaring (or fast-powering)?

Answer 45

no :/

Answer 46

Have you learned any other method to exponentiate other than just do it the slow way?

Answer 47

I don't remember covering a method. What would we be using it for?

Answer 48

Almost certainly fast powering/successive squaring.

Answer 49

It's possible we covered successive squaring in class, however, I'm having trouble remembering how it would be done.

Answer 50

Well, I'll walk you through the process in this example, and hopefully that'll refresh your memory.

Answer 51

sounds great :)

Answer 52

First, we need to write the exponent (e.g. 47) as powers of 2. So \[47=2^5+2^3+2^2+2^1+1\]So\[25^{47}\equiv25\cdot25^2\cdot25^{2^2}\cdot25^{2^3}\cdot25^{2^5}\pmod{77}\]

Answer 53

Now observe that \[25^{2^n}=(25^{2^{n-1}})^2\]So we only have to square things a whole bunch of times. So, \[25^2\equiv625\equiv 9\pmod{77}\]\[25^{2^2}\equiv9^2\equiv81\equiv4\pmod{77}\]\[25^{2^3}\equiv4^2\equiv16\pmod{77}\]\[25^{2^4}\equiv16^2\equiv256\equiv 25\pmod{77}\]\[25^{2^5}\equiv25^2\equiv9\pmod{77}\]Thus,\[25^{47}\equiv25\cdot9\cdot4\cdot16\cdot9\pmod{77}\]

Answer 54

Ah ok, now I understand why you did the step before.

Answer 55

So that basically breaks 25^47 down into its multiples

Answer 56

Exactly. Each of these numbers is relatively small, and can be multiplied relatively easily. For example:\[25\cdot9\equiv25\cdot3\cdot3\equiv75\cdot3\equiv-2\cdot3\equiv-6\pmod{77}\]

Answer 57

how is the 75*3 congruent to -2*3 though?

Answer 58

That's since \(75\equiv-2\pmod{77}\).

Answer 59

ohhh right

Answer 60

So then how would we find the m value using the work above?

Answer 61

Just multiply the whole thing out and simplify one step at a time. I think you're capable of doing that.\[25\cdot9\cdot4\cdot16\cdot9\equiv?\pmod{77}\]

Answer 62

Do I need to do the same kind of thing you did here?

25⋅9≡25⋅3⋅3≡75⋅3≡−2⋅3≡−6(mod77)

Answer 63

You don't need to, but it can make the computations easier.

Answer 64

Alright so,

25*9*4*16*9 = 25*3*3*4*16*3*3 = -2*3*-13*3*3 = -2*-13*27

err, I don't know that I'm doing this right

Answer 65

So far it looks fine. Try writing it as\[-2\cdot-13\cdot27=((-2\cdot-13)\cdot3)\cdot9\]And multiplying that out mod 77.

Answer 66

So, ((26)*3)*9 = 1*9 = 9 mod 77

Answer 67

Perfect. So \(m=9\).

Answer 68

Awesome. :D

Answer 69

Thank you so much for all the help! Think I'm starting to understand this stuff :)

Answer 70

You're welcome. Stuff like this just takes some practice, and it'll start going a lot faster.

Answer 71

Yeah for sure, well I think this really helped me start to understand how to go about these type of problems a bit. And I also understand how Euclid's Algorithm works better too, which will be very useful in some more homework problems.

Answer 72

Excellent. Before I leave I should mention that there are other ways of finding inverses/computing powers of numbers in situations like this. In particular, if you're given an integer \(a\) and asked to find \(a^{-1}\), you can again apply Euler's theorem to see that\[a^{-1}\equiv a^{\phi(n)-1}\pmod{n}\]So if we were to use this above, we would have had to calculate\[23^{\phi(60)-1}\equiv23^{15}\pmod{60}\]

Answer 73

As for finding \(a^b\pmod{pq}\), where \(p,q\) are primes, we could have applied the chinese remainder theorem. In this way, you would calculate
\[a^b\pmod{p}\]\[a^b\pmod{q}\]and then use the chinese remainder theorem to find \(a^b\pmod{pq}\).

Answer 74

Once you're familiar enough with these various techniques, you can start seeing how to combine them to do computations very quickly and efficiently.

Answer 75

Interesting, I can see how that method would speed things up though.

Answer 76

Well thanks again for the help. I appreciate all the time you spent helping me understand the problem. It's really nice to be able to walk through problems at a pace where I can actually understand what I am doing. I will definitely look into the chinese remainder theorem. Might be useful on another homework.

Answer 77

If you're interested at looking at an example, this is a problem I posted last year that used the chinese remained theorem to greatly simplify an exponential. There's not much work shown in the comments, but if you think about it you should eventually see the path that I took to solve it.

http://openstudy.com/users/kinggeorge#/updates/4fe2a165e4b06e92b8718a43

Answer 78

Awesome, I'll look over it and see if I can understand it.

Answer 79

Looks complicated, haha, I think I would need more practice and further explanation to understand it completely.

Answer 80

All of the techniques used are actually fairly simple, with the Chinese remainder theorem the most complex. It's just the way you can chain the different techniques together.

Answer 81

I see, so I guess a lot of it is fairly similar to what we just did.

Answer 82

Exactly.