📄 387-391.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=387-391//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="385-387.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="391-392.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<H4 ALIGN="LEFT"><A NAME="Heading19"></A><FONT COLOR="#000077">Exponentiation Operations</FONT></H4>
<P>While it is possible to attempt to raise a number to a large power, doing so will more than likely exhaust the capacity of your computer as there is a finite limit to the size of integers on each computer. Instead of directly raising a number to a power, you can do the modular reduction after each multiply operation. For example, assume you want to compute 123<SUP>7</SUP> mod 456. Instead of computing 123 multiplied by itself 7 times and then dividing by 456 to obtain the remainder, let’s do modular reduction after each multiply. That is:</P>
<!-- CODE SNIP //-->
<PRE>
123<SUP>2</SUP> = 123*123 = 15129 mod 456 = 81 mod 456
123<SUP>3</SUP> = 123*81 mod 456 = 9963 mod 456 = 387 mod 456
123<SUP>4</SUP> = 123*387 mod 456 = 47601 mod 456 = 177 mod 456
123<SUP>5</SUP> = 123*177 mod 456 = 21771 mod 456 = 339 mod 456
123<SUP>6</SUP> = 123*339 mod 456 = 41697 mod 456 = 201 mod 456
123<SUP>7</SUP> = 123*201 mod 456 = 24723 mod 456 = 99 mod 456
</PRE>
<!-- END CODE SNIP //-->
<P>While the preceding method reduces the computation to a series of seven small multiplies and seven small divides, most exponents used with RSA are considerably larger. This means that you would more than likely want to obtain a more efficient method to compute exponents.
</P>
<P>To raise a number <I>x</I> to an exponent, you can perform a series of squaring operations. For example:</P>
<!-- CODE SNIP //-->
<PRE>
123<SUP>2</SUP> = 123*123 = 15129 mod 456 = 81 mod 456
123<SUP>4</SUP> = 81*81 = 6561 mod 456 = 177 mod 456
</PRE>
<!-- END CODE SNIP //-->
<P>While you could continue and square 123 again, obtaining the value of 123<SUP>8</SUP>, unfortunately the 123<SUP>7</SUP> that you require is not a power of 2. However, if you know what 123<SUP>x</SUP> is, then it is relatively easy to compute 123<SUP>2<I>x</I></SUP>, since you obtain that by squaring 123<SUP><I>x</I></SUP>. Similarly, you can compute 123<SUP>2<I>x</I>+1</SUP>, as all you need to do is multiply the result obtained by squaring 123<SUP><I>x</I></SUP> (123<SUP>2<I>x</I></SUP>) by 123. This means you can perform a sequence of squaring operations to obtain the nearest power of two to the exponent you require, and then multiply the result <I>n</I> times, where <I>n</I> is the difference between the exponent you seek and the nearest computed power of 2. For example:</P>
<!-- CODE SNIP //-->
<PRE>
123<SUP>7</SUP> mod 456 = 123<SUP>2</SUP> * 123<SUP>2</SUP> * 123 * 123 * 123 mod 456
123<SUP>4</SUP> mod 456 = 177 mod 456
</PRE>
<!-- END CODE SNIP //-->
<P>Then:
</P>
<!-- CODE SNIP //-->
<PRE>
123<SUP>7</SUP> mod 456 = 123*123*123*177 mod 456
= 123*123*339 mod 456
= 123*201 mod 456
= 99 mod 456
</PRE>
<!-- END CODE SNIP //-->
<P>Note that the preceding method required two squaring and three multiplication operations. You can reduce the number of operations further if you note that 123<SUP>a</SUP>*123<SUP>b</SUP> = 123<SUP>a+b</SUP>. This means given:</P>
<!-- CODE SNIP //-->
<PRE>
123<SUP>2</SUP> mod 456 = 81 mod 456
123<SUP>7</SUP> mod 456 = 387 mod 456
</PRE>
<!-- END CODE SNIP //-->
<P>you would compute the following:
</P>
<!-- CODE SNIP //-->
<PRE>
123<SUP>6</SUP> = 123<SUP>2</SUP>*123<SUP>4</SUP> = 81.387 mod 456 = 339 mod 456
123<SUP>7</SUP> = 123*123<SUP>6</SUP> = 123.339 mod 456 = 99 mod 456
</PRE>
<!-- END CODE SNIP //-->
<P>Note that in this example you would compute 123<SUP>2</SUP> mod 456, 123<SUP>4</SUP> mod 456, 123<SUP>6</SUP> mod 456, and then multiply the last result by 123. This reduces the number of computations to two squares and two multiplies.</P>
<P>If you convert the exponent to binary, you can compute 123 raised to a sequence of powers. For example, 7 is 111<SUB>2</SUB> which represents the sequence 1<SUB>2</SUB>, 11<SUB>2</SUB>, 111<SUB>2</SUB>. Note that each successive power concatenates one additional bit of the desired exponent. Also note that each successive power (from the most significant bit position) is either twice the preceding power or once or more than twice the preceding power. Thus, you can raise 123 to the first, third, and seventh power by repeated squaring together with multiplication by 123 for the bits that are 1. For example, commencing with the first power you start with:</P>
<!-- CODE SNIP //-->
<PRE>
123 mod 456
</PRE>
<!-- END CODE SNIP //-->
<P>To obtain the third power, you would multiply 123 by its square, i.e., 123 (123<SUP>2</SUP>). To then obtain the seventh power, you would obtain the sixth power (123<SUP>3</SUP>)<SUP>2</SUP> and multiply by 123. Thus, raising 123 to the seventh power can be accomplished by repeated squaring and, as required, multiplying by 123 for the bits that are 1. Focusing on exponents:</P>
<!-- CODE SNIP //-->
<PRE>
7 = (((1)<SUP>2</SUP> + 1)<SUP>2</SUP> +1)
</PRE>
<!-- END CODE SNIP //-->
<P>Then you obtain:
</P>
<!-- CODE SNIP //-->
<PRE>
123<SUP>7</SUP> = (((123)<SUP>2</SUP> * 123)<SUP>2</SUP> * 123)
</PRE>
<!-- END CODE SNIP //-->
<P>Using the preceding method you can perform exponentiation of a base to an exponent as follows:
</P>
<DL>
<DD><B>1.</B> Commence by setting an initial value to 1.
<DD><B>2.</B> Convert the exponent to binary.
<DD><B>3.</B> Read the binary value of the exponent bit by bit from high order to low order and square your value for each position. If the value of the bit position is 1, then multiply by the base. After each operation, perform modular reduction to maintain a relatively small intermediate result.
</DL>
<P>Now that you have an appreciation for techniques to facilitate exponentiation, let’s return to the key computation process. It was noted previously that the inverse of 41 mod 3233 is:
</P>
<!-- CODE SNIP //-->
<PRE>
41<SUP>3231</SUP> mod 3233
</PRE>
<!-- END CODE SNIP //-->
<P>Note that 3231 is 110010011111<SUB>2</SUB>. This means you can compute 41 raised to the 3231 power by squaring 12 times and multiplying 8 times. Although I will leave it as an exercise for you to compute, let’s assume the answer was <I>x</I>. You would then publish <I>e</I> and <I>n</I> and keep the value <I>x</I> which represents your secret decryption key. Suppose you want to encrypt the famous message ABADABA… Then, the ASCII value of your message <I>m</I> is:</P>
<!-- CODE SNIP //-->
<PRE>
m = 64656467646564…
</PRE>
<!-- END CODE SNIP //-->
<P>To facilitate computations you would break the message into small blocks. For example:
</P>
<!-- CODE SNIP //-->
<PRE>
m<SUB>1</SUB> = 6465
m<SUB>2</SUB> = 6467
m<SUB>3</SUB> = 6465
</PRE>
<!-- END CODE SNIP //-->
<P>and so on.
</P>
<P>Using the encryption key of 41, the first block would be encrypted as:</P>
<!-- CODE SNIP //-->
<PRE>
c<SUB>1</SUB> = 6465<SUP>41</SUP> mod 3233
</PRE>
<!-- END CODE SNIP //-->
<P>Similarly, the second block would be encrypted as follows:
</P>
<!-- CODE SNIP //-->
<PRE>
c<SUB>2</SUB> = 6467<SUP>41</SUP> mod 3233
</PRE>
<!-- END CODE SNIP //-->
<P>You would continue the same operation on the remaining blocks until you generated the entire encrypted message. As previously discussed, decryption would be performed on a block by block (c<SUB>1</SUB>, c<SUB>2</SUB>…) basis, performing the same exponentiation but using the decryption key whose value is <I>x</I>. Thus:</P>
<!-- CODE SNIP //-->
<PRE>
m<SUB>1</SUB> = c<SUB>1</SUB><SUP>x</SUP> mod 3233
m<SUP>2</SUP> = c<SUB>2</SUB><SUP>x</SUP> mod 3233
</PRE>
<!-- END CODE SNIP //-->
<P>and so on.
</P><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="385-387.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="391-392.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
</body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -