maths.free › Number Theory › RSA: cryptography from number theory

RSA: cryptography from number theory

Public keys from two primes, and why factoring is the lock.

Choose primes p, q; n = pq; pick e coprime to φ(n) = (p − 1)(q − 1); the private key d is e⁻¹ mod φ(n). Encrypt mᵉ mod n, decrypt with d. The security is the difficulty of factoring n. Picture it: a padlock anyone can snap shut (e) that only the key (d) opens. Think it: correctness is Euler's theorem; the whole scheme is one modular inverse.

କାର୍ଯ୍ୟକାରୀ ଉଦାହରଣ · inverse of 17 mod 3120

Number-Theory · Modular-Arithmetic

Inverse of 17 mod 3120

17,\ 3120

ପଦକ୍ଷେପ କ୍ରମେ

  1. 17x \equiv 1 \pmod{3120}

    We want x with a·x ≡ 1 (mod m). It exists only when gcd(a, m) = 1.

  2. 3120 = 183 \times 17 + 9

    Euclid step.

  3. 17 = 1 \times 9 + 8

    Euclid step.

  4. 9 = 1 \times 8 + 1

    Euclid step.

  5. 8 = 8 \times 1 + 0

    Euclid step.

  6. 17 \times 2753 = 46801 \equiv 1 \pmod{3120}

    Back-substitute (extended Euclid) to express 1 as a combination of a and m; the coefficient of a is the inverse.

ଉତ୍ତରକୁ ଖୋଲନ୍ତୁ
17^{-1} \equiv 2753 \pmod{3120}

ଏବେ ଆପଣ ଗୋଟିଏ ସମସ୍ୟା ବାଛନ୍ତୁ, କିମ୍ବା ଆପଣଙ୍କର ନିଜ ସମସ୍ୟାକୁ ଟାଇପ କରନ୍ତୁ କିମ୍ବା ଆଙ୍କନ୍ତୁ। ପ୍ରତ୍ୟେକ ପର୍ଯ୍ୟାୟରେ, ଗୋଟିଏ ଚିତ୍ର, ଉତ୍ତର ଲୁକ୍କାୟିତ ହୋଇଥାଏ ଯେ ପର୍ଯ୍ୟନ୍ତ ଆପଣ ପଚାରନ୍ତି ନାହିଁ।

ଆପଣଙ୍କର ନିଜ କାର୍ଯ୍ୟକୁ ବଜାୟ ରଖନ୍ତୁ

ଗୋଟିଏ ମୁକ୍ତ ଖାତା ପ୍ରତ୍ୟେକ ପାଠରେ ଟିପ୍ପଣୀ ଯୋଗ କରିଥାଏ, ଆପଣ ଯାହା ସମାପ୍ତ କରିଛନ୍ତି ତାହାର ଗୋଟିଏ ରେକର୍ଡ, ଆପଣଙ୍କର ସମାଧାନ ହୋଇଥିବା ସମସ୍ୟାଗୁଡ଼ିକ ଗୋଟିଏ ସ୍ଥାନରେ, ଏବଂ ଜଣେ ଶିକ୍ଷକ ଆପଣ ଏହି ପୃଷ୍ଠା ବିଷୟରେ ପଚାରିପାରିବେ। ଗଣିତ ନିଜେ ସମସ୍ତଙ୍କୁ ଖୋଲା ଅଛି, ଲଗଇନ ହୋଇଥିବା କିମ୍ବା ନଥିବା।

ସଦସ୍ୟତା ନିଅନ୍ତୁ ଲଗଇନ

ଏଠାରେ ବ୍ୟବହୃତ ପ୍ରତୀକଗୁଡିକ

ସମ୍ପୂର୍ଣ୍ଣ ବର୍ଣ୍ଣନା ପାଇଁ ଯେକୌଣସି ପ୍ରତୀକକୁ ଟ୍ୟାପ କରନ୍ତୁ, ଗୋଟିଏ ଚିତ୍ର, ଏବଂ ଏଥିରେ ଥିବା ପ୍ରତ୍ୟେକ ଅକ୍ଷରର ଅର୍ଥ କଣ।

କିପରି: RSA: cryptography from number theory

  1. We want x with a·x ≡ 1 (mod m). It exists only when gcd(a, m) = 1.
  2. Euclid step.
  3. Euclid step.
  4. Euclid step.
  5. Euclid step.
  6. Back-substitute (extended Euclid) to express 1 as a combination of a and m; the coefficient of a is the inverse.

ଲୋକମାନେ ପଚାରୁଥିବା ପ୍ରଶ୍ନ

Why are primes so important?

Every integer factors into primes in exactly one way, so primes are the atoms of multiplication. Cryptography relies on that factoring being easy to state and hard to do.

How do I tell whether a big number is prime?

Trial division up to the square root works for small numbers. For large ones, probabilistic tests (Miller-Rabin) give an answer that is wrong with negligible probability, and deterministic tests (AKS) exist but are slower.

ଅଧିକ Number Theory

Prime factorisationPrime numbersGCD and LCMModular arithmeticDivisorsSequencesNumber basesDiophantine equationsFermat's little theorem and Euler's theorem