PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (230)
Orphanage
Unclass'd
Unproven (519)
Corrections (16)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Medium Entry average rating: Very high
RSA (Definition)

RSA is an example of public key cryptography. It is a widely used system, relying for its security on the difficulty of factoring a large number.

Alice forms her public and private keys as follows:

  • Chooses large primes $ p$ and $ q$, then form $ n=pq$.
  • Chooses e coprime with $ \phi (n) = (p-1)(q-1)$.
  • Publishes $ (n,e)$ as her public key.
  • Computes private key $ d$ such that $ de \equiv 1 \quad\textrm{mod } \phi(n)$.

To encrypt a message $ M$ (where $ M < n$) the user Bob forms $ C = M^e \quad\textrm{mod } n$.

To decrypt the message, Alice forms $ d(C) = C^d \quad\textrm{mod } n$.

This recovers message $ M$ because:

$\displaystyle d(C)$ $\displaystyle = C^d \quad\textrm{mod } n$    
  $\displaystyle = (M^e + rn)^d \quad\textrm{mod } n \qquad \textrm{for some }r$    
  $\displaystyle = (M^{(p-1)})^{t(q-1)}M \quad\textrm{mod } n \qquad \textrm{for some }t$    
  $\displaystyle \equiv (1+sp)^{t(q-1)}M \quad\textrm{mod } p \qquad \textrm{for some }s$    
  $\displaystyle \equiv M \quad\textrm{mod } p$    

So $ d(C) \equiv M \quad\textrm{mod } p$ and similarly, $ d(C) \equiv M \quad\textrm{mod } q$ so by the Chinese remainder theorem, $ d(C) \equiv M \quad\textrm{mod } n$, and since we know $ M<n$ we know that $ M = d(C)$.



"RSA" is owned by aoh45. [ full author list (2) ]
(view preamble)

View style:

Other names:  RSA cryptosystem
Log in to rate this entry.
(view current ratings)

Cross-references: Chinese remainder theorem, coprime, primes, chooses, number, public key cryptography
There are 5 references to this entry.

This is version 2 of RSA, born on 2005-05-08, modified 2008-06-29.
Object id is 7025, canonical name is RSA.
Accessed 2383 times total.

Classification:
AMS MSC: 94A60 (Information and communication, circuits :: Communication, information :: Cryptography)
Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)