RSA
1. Pick two large prime numbers p,q (p <> q)
2. Set n=pq
3. Set φ = (p-1)(q-1) (φ the Euler totient function for n)
4. Pick e such that: 1<e<φ, and GCD(e, φ) = 1 (e and φ relatively prime (coprime))
5. Set d such that: d e ≡ 1 (modulo φ)
So for message m to be cyphered to c:
برای مثال مجموعهٔ Z۱۷ را در نظر میگیریم. این مجموعه به صورت {۱۶,...,۱,۲} میباشد که مجموعهٔ باقیماندهها در تقسیم به عدد اول ۱۷ = p هستند.
ابتدا در این مجموعه عمل توان گسسته را در نظر میگیریم. برای محاسبهٔ ۳۴ در این مجموعه، کافی است نخست ۸۱ = ۳۴ را محاسبه نموده و سپس باقیماندهٔ تقسیم حاصل به ۱۷ = p را به دست آوریم: ۸۱mod ۱۷ = ۱۳
محاسبهٔ لگاریتم گسسته عکس این عمل خواهد بود، به این صورت که در همنهشتی به پیمانهٔ ۱۷ = p (یا به عبارت دیگر در مجموعهٔ Z۱۷) لگاریتم گسستهٔ عدد ۱۳ در مبنای ۳ برابر با ۴ میباشد.
مسألهٔ لگاریتم گسسته یکی از مسائل دشوار ریاضی است و معکوس آن یعنی محاسبهٔ توان گسسته به سادگی قابل انجام است. این عدم تقارن در دشواری دو مسألهٔ معکوس، برای تحقق سیستمهای رمزنگاری مختلفی مورد استفاده قرار گرفته است که از آن جمله میتوان به این موارد اشاره کرد:
How to Make RSA Uncrackable
Of course, in our case the factors of R can be found by consulting a
times table. So it's not much of a challenge. (For that matter, since
we're encrypting one character at a time, our coded messages would
also be vulnerable to good old-fashioned cryptanalysis).
To make it less easy to find R's factors, we need to pick larger prime
numbers for U and V to begin with. If, instead of 5 and 11, we had
chosen 673 and 24971, we would have a value of 16805483 for R, and
phi(R) would be 16779840. (This would also give us enough room to
encrypt more than one byte at a time, which seriously reduces the
vulnerability to cryptanalysis.) Looking for a P and Q pair is no
longer something you want to do with pencil and paper, of course, but
it took me less than three minutes to find the usable pair 397 and
211333 -- including the time it took to write and debug a Perl script.
On the other hand, it also took me less than three seconds to run
"factor" on 16805483 to obtain 673 and 24971. Armed with those
numbers, it wouldn't take much longer to derive 211333 from 397. So
even these numbers aren't close to being large enough. We need
really big numbers.
Well, we can certainly find huge values for R that are difficult to
factor. But how far can we go before it becomes too difficult for us
to use the number in the first place?