Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I´m trying to follow one of the very detailed RSA Proofs given by di-mgt: "RSA theory", but unfortunately I stuck at the beginning of solution (chapter 3).

I don´t understand where the second part of (8) is coming from:

$RsaPrivate(RsaPublic(m))\ =\ (m^e\ mod\ n)^d\ mod\ n\ =\ m^{ed}\ mod\ n$

How is it reduced? Where can I find this rule?

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

You'll probably know this relation, which should be obvious if you think about it:

$$(a \bmod n) + (b \bmod n) \equiv a + b \mod n$$

This means that when using addition you do not have to reduce the operands, only the final result. However, if the final result is an operand again it needs not be reduce. This means that long chains of modular additions can be computed using normal additions with one reduction at the end.

You can see $a\times n$ as a series of additions:

$$a\times n = \overbrace{ a + \cdots + a }^{n \text{ times}}$$

You can see $a^b$ as a series of multiplications:

$$a^b = \overbrace{ a \times \cdots \times a }^{b \text{ times}}$$

So we can see $a^b$ as a very long series of additions of the base. Thus we do not need to reduce the base:

$$(a \bmod n)^b \equiv a^b \mod n$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.