Exercise · ZW-RSA-CRYPTOSYSTEM-010 · ★★★ Advanced

With \( p = 3 \), \( q = 11 \) and \( e = 7 \), check whether \( e \) is valid, find \( d \), and verify that \( 4^{ed} \equiv 4 \pmod{33} \).

Choose one option.

Show answer
  • A. Valid, \( d = 3 \), and the check gives 4

Explanation

Since gcd(7, 20) = 1 and 7·3 = 21 ≡ 1 (mod 20), e is valid with d = 3, and 4^{21} ≡ 4 (mod 33). The option claiming invalidity relies on a wrong gcd computation.

Study Elementary number theory in ZWMath →

Review the concept: RSA cryptosystem

The RSA cryptosystem is a public-key encryption method based on the difficulty of factoring the product of two large primes. It uses Euler's theorem and modular inverses to encrypt and decrypt messages.

\[c \equiv m^{e} \pmod{n}, \quad m \equiv c^{d} \pmod{n}\]

More practice problems: rsa cryptosystem

← ZW-RSA-CRYPTOSYSTEM-009