📄 385-387.html
字号:
<html><head><TITLE>Learn Encryption Techniques with BASIC and C++:Public Key Encryption</TITLE>
<!-- BEGIN HEADER --><META NAME="ROBOTS" CONTENT="NOINDEX, NOFOLLOW"><SCRIPT><!--function displayWindow(url, width, height) { var Win = window.open(url,"displayWindow",'width=' + width +',height=' + height + ',resizable=1,scrollbars=yes');}//--></SCRIPT></HEAD><body bgcolor="ffffff" link="#006666" alink="#006666" vlink="#006666"><P>
<CENTER><B>Learn Encryption Techniques with BASIC and C++</B>
<FONT SIZE="-2">
<BR>
<I>(Publisher: Wordware Publishing, Inc.)</I>
<BR>
Author(s): Gil Held
<BR>
ISBN: 1556225989
<BR>
Publication Date: 10/01/98
</FONT></CENTER>
<P>
<!-- Empty Reference Subhead -->
<!--ISBN=1556225989//-->
<!--TITLE=Learn Encryption Techniques with BASIC and C++//-->
<!--AUTHOR=Gilbert Held//-->
<!--PUBLISHER=Wordware Publishing, Inc.//-->
<!--CHAPTER=8//-->
<!--PAGES=385-387//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="382-385.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="387-391.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<H3><A NAME="Heading15"></A><FONT COLOR="#000077">RSA</FONT></H3>
<P>RSA is a public key encryption system invented by Rivest, Shamir, and Adleman in 1978. Under this technique, both encryption and decryption are performed using exponentiation. RSA obtains security from the difficulty associated with factoring large prime numbers. As you will shortly note, public and private keys are functions of a pair of large prime numbers. Thus, the ability to decipher plaintext from the use of a public key and ciphertext is the equivalent of factoring two large primes.
</P>
<P>Using the RSA system, each party generates a public key and a corresponding private key. To do so, two large primes of equal length are selected, <I>p</I> and <I>q</I>. To facilitate security, each prime should be a minimum of 32 bytes, or 256 bits, in length. Once the two primes are selected, you multiply them together and find their product <I>n</I>, which is referred to as the modulus of <I>pq</I>.</P>
<H4 ALIGN="LEFT"><A NAME="Heading16"></A><FONT COLOR="#000077">Public Key Generation</FONT></H4>
<P>To generate a public key, each person using the RSA algorithm generates their encryption (<I>e</I>) and decryption (<I>d</I>) keys. The encryption key, <I>e</I>, is selected such that it is less than <I>n</I> and relatively prime to (<I>p</I>-1)(<I>q</I>-1), which represents the totient function 0(<I>n</I>). This means that <I>e</I> and (<I>p</I>-1)(<I>q</I>-1) have no common factors other than 1. Your public key then becomes the pair <<I>e</I>,<I>n</I>>.</P>
<H4 ALIGN="LEFT"><A NAME="Heading17"></A><FONT COLOR="#000077">Private Key Generation</FONT></H4>
<P>To compute your private key, you will find another number <I>d</I>, such that (<I>ed</I>-1) is divisible by (<I>p</I>-1)(<I>q</I>-1). That is, <I>d</I> represents the multiplicative inverse of <I>e</I> mod 0(<I>n</I>). Then, the private key becomes the pair <<I>d</I>,<I>n</I>>. Once your public and private keys are selected, the primes <I>p</I> and <I>q</I> are no longer needed. Although it is safe to discard them, they should not be revealed.</P>
<H4 ALIGN="LEFT"><A NAME="Heading18"></A><FONT COLOR="#000077">Message Encipherment</FONT></H4>
<P>To encipher a message <I>m</I> you would first subdivide it into blocks smaller than <I>n</I> (<I>m</I><<I>n</I>). When working with binary data this would be equivalent to selecting the largest power of 2 less than <I>n</I>. You would then use your public key (<I>e</I>) to compute ciphertext (<I>c</I>) as follows:</P>
<!-- CODE SNIP //-->
<PRE>
c = m<SUB>i</SUB><SUP>e</SUP> mod n
</PRE>
<!-- END CODE SNIP //-->
<P>where <I>m<SUB>i</SUB></I> represents block <I>I</I> of message <I>m</I>.</P>
<P>To decrypt a message you would use your private key (<I>d</I>) on each ciphertext block <I>c<SUB>i</SUB></I> as follows:</P>
<!-- CODE SNIP //-->
<PRE>
m<SUB>i</SUB> = c<SUB>i</SUB><SUP>d</SUP> mod n
</PRE>
<!-- END CODE SNIP //-->
<P>To illustrate the use of RSA, let’s use a few small primes to facilitate observing the relevant computations. First, let’s assume you selected <I>p</I> = 53 and <I>q</I> = 61. Then:</P>
<!-- CODE SNIP //-->
<PRE>
n = p*q = 53*61 = 3233
</PRE>
<!-- END CODE SNIP //-->
<P>Next you would randomly select an encryption key, <I>e</I>, such that it has no common factors with 3233. For our example, let’s select <I>e</I> to be 41. Then, the private key <I>d</I> would be:</P>
<!-- CODE SNIP //-->
<PRE>
d = 41<SUP>-1</SUP> mod 3233
</PRE>
<!-- END CODE SNIP //-->
<P>To compute <I>d</I>, you must obtain the multiplicative inverse of 41 mod 3233. That is, you must determine the number which when multiplied by 41 mod 3233 yields a result of unity. Based upon Euler’s application of the totient function, if <I>n</I> is a prime, the 0(<I>n</I>) = <I>n</I>-1. If <I>p</I> and <I>q</I> are primes and <I>n</I> = <I>pq</I>, then 0(<I>n</I>) = (<I>p</I>-1)(<I>q</I>-1). Thus, if the gcd (<I>a</I>,<I>n</I>) = 1, where <I>x</I> is not a multiple of <I>n</I>, then:</P>
<!-- CODE SNIP //-->
<PRE>
x<SUP>0(n)</SUP> mod n = 1
</PRE>
<!-- END CODE SNIP //-->
<P>This means you can compute the multiplicative inverse <I>x</I><SUP>-1</SUP> mod <I>n</I> as follows:</P>
<!-- CODE SNIP //-->
<PRE>
X = x<SUP>0(n)</SUP>-1 mod n
</PRE>
<!-- END CODE SNIP //-->
<P>Returning to your computation, you need to determine the private key <I>d</I>, such that:</P>
<!-- CODE SNIP //-->
<PRE>
d = 41<SUP>-1</SUP> mod 3233
</PRE>
<!-- END CODE SNIP //-->
<P>Since 3233 is prime, then 0(3233) = 3233-1 = 3232. Thus, the inverse of 41 mod 3233 becomes:
</P>
<!-- CODE SNIP //-->
<PRE>
41<SUP>3232-1</SUP> mod 3233 = 41<SUP>3231</SUP> mod 3233
</PRE>
<!-- END CODE SNIP //-->
<P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="382-385.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="387-391.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
</body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -