📄 382-385.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=382-385//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="378-381.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="385-387.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<H4 ALIGN="LEFT"><A NAME="Heading13"></A><FONT COLOR="#000077">The Euclidean Algorithm</FONT></H4>
<P>It was briefly mentioned previously that the Euclidean algorithm provides a mechanism to find the multiplicative inverse mod <I>n</I>. Both the Euclidean algorithm and a function developed by Euler known as the totient function play an important role in public key encryption. Thus, prior to directing your attention to a public key algorithm, an additional review of an algorithm and function is warranted.</P>
<P>As you might expect, the Euclidean algorithm was invented by Euclid. While it is conjectured that Euclid was attempting to determine a method to find the greatest common divisor (gcd) of two integers, resulting in the algorithm holding his name, his algorithm can also be used to determine the multiplicative inverse mod <I>n</I>. Thus, it holds an important role in several public key encryption methods.</P>
<P>As a review, the greatest common divisor of two integers is the largest integer that evenly divides both. If the greatest common divisor of two numbers is 1, then those numbers are relatively prime. This means that an algorithm that enables you to efficiently find the gcd of two integers can also determine if the gcd of the two integers is relatively prime. As you will shortly note, if the gcd of two integers is relatively prime, you can find their multiplicative inverse. For example, if you want to find the multiplicative inverse of <I>m</I> mod <I>n</I>, this means you need to find a number μ such that μ<I>m</I> = 1 mod <I>n</I>. This means that μ<I>m</I> differs from 1 by a multiple of <I>n</I>. This also means that there is an integer <I>v</I>, such that μ<I>n</I> + <I>vm</I> = 1. As you will soon note, you can use Euclid’s algorithm to find μ and <I>v</I> provided gcd(<I>m</I>,<I>n</I>) = 1. If <I>m</I> and <I>n</I> are not relatively prime, you will not be able to determine μ and <I>v</I>, which means that <I>m</I> does not have a multiplicative inverse mod <I>n</I>.</P>
<P>To illustrate the Euclidean algorithm, let’s assume you want to compute the gcd of 432 and 252. If you assume the pair <I>x</I>,<I>y</I> with <I>y</I><<I>x</I>, then the smaller number <I>y</I> will have a divisor D such that <I>x</I>-<I>y</I>, <I>x</I>-2<I>y</I>, etc., also have that divisor unless one of them is zero, a situation which indicates that <I>y</I> divides <I>x</I> and <I>y</I> is the gcd. Thus, you can take <I>x</I>-<I>ny</I> where <I>n</I> is the integer result of dividing <I>x</I> by <I>y</I>, and <I>x</I>-<I>ny</I> is the remainder, which is less than <I>x</I>.</P>
<P>The top portion of Figure 8.5 illustrates generic coding for finding the gcd using the Euclidean algorithm. The lower portion of Figure 8.5 illustrates the use of the Euclidian algorithm for finding the gcd of 432 and 252. Starting with 432 (<I>a</I>) and 252 (<I>b</I>), you divide <I>a</I> by <I>b</I> and store the remainder of 180 (<I>c</I>). Next you divide <I>b</I> by <I>c</I> and take the remainder of 72 as <I>d</I>. You repeat this sequence of operations until you obtain a zero remainder. The last number before zero, which is 2, is the gcd. If the two numbers have no other common divisor, the number 1 will be the result, indicating that they are relatively prime. An example of the use of the Euclidean algorithm to determine that two numbers have no other common divisor than 1 is shown in Figure 8.6.</P>
<P><A NAME="Fig5"></A><A HREF="javascript:displayWindow('images/08-05.jpg',374,342 )"><IMG SRC="images/08-05t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/08-05.jpg',374,342)"><FONT COLOR="#000077"><B>Figure 8.5</B></FONT></A> Finding the greatest common divisor using the Euclidean algorithm.</P>
<P><A NAME="Fig6"></A><A HREF="javascript:displayWindow('images/08-06.jpg',376,133 )"><IMG SRC="images/08-06t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/08-06.jpg',376,133)"><FONT COLOR="#000077"><B>Figure 8.6</B></FONT></A> Using the Euclidean algorithm to determine that 19 and 3 are relatively prime to one another.</P>
<H4 ALIGN="LEFT"><A NAME="Heading14"></A><FONT COLOR="#000077">The Totient Function</FONT></H4>
<P>The symbol 0 is known as the totient function, supposedly a contraction of the terms total and quotient. Through the use of the totient function, you can determine how many numbers less than <I>n</I> are relatively prime to <I>n</I>. For example, if <I>n</I> is prime, then the set of integers {1, 2, … <I>n</I>-1} are relatively prime to <I>n</I>, resulting in 0(<I>n</I>) = <I>n</I>-1. If you assume <I>n</I> is a product of two distinct primes, <I>p</I> and <I>q</I>, then there are (<I>p</I>-1)*(<I>q</I>-1) numbers relatively prime to <I>n</I>, resulting in 0(<I>n</I>) = (<I>p</I>-1)(<I>q</I>-1).</P>
<P>As previously indicated, when you construct a table of modulo exponentiation you will note that the results in certain columns are the same. Based upon the research of mathematicians, it turns out that <I>x<SUP>y</SUP></I> mod <I>n</I> is the same as <I>x</I><SUP>(<I>y</I> mod 0 (<I>n</I>))</SUP> mod <I>n</I>. For example, assume <I>x</I> = 2 and <I>y</I> = 2. The numbers relatively prime to 10 are {1, 3, 7, 9}, therefore 0(10) = 4. Then:</P>
<!-- CODE SNIP //-->
<PRE>
x<SUP>y</SUP> mod n = 2<SUP>2</SUP> mod 10 = 4
</PRE>
<!-- END CODE SNIP //-->
<P>and
</P>
<!-- CODE SNIP //-->
<PRE>
x<SUP>(y mod 0(n))</SUP> mod n = 2<SUP>(2 mod 4)</SUP> mod 10 = 4
</PRE>
<!-- END CODE SNIP //-->
<P>and
</P>
<!-- CODE SNIP //-->
<PRE>
y = 3.
</PRE>
<!-- END CODE SNIP //-->
<P>Then:
</P>
<!-- CODE SNIP //-->
<PRE>
x<SUP>y</SUP> mod 10 = 5<SUP>3</SUP> mod 10 = 5
</PRE>
<!-- END CODE SNIP //-->
<P>and
</P>
<!-- CODE SNIP //-->
<PRE>
x<SUP>(y mod 0(n))</SUP> mod n = 5<SUP>(3 mod 4)</SUP> mod 10 = 5
</PRE>
<!-- END CODE SNIP //-->
<P>The use of the preceding formulas as equivalency is true for all values of <I>n</I> that are primes or any product of distinct primes. One important special case of the preceding is where <I>y</I> = 1 mod 0(<I>n</I>). In this situation, for any number <I>x</I>, <I>x<SUP>y</SUP></I> = <I>x</I> mod <I>n</I>, which forms the basis for the RSA public key encryption system.</P>
<P>Once you determine a number is a prime through the use of the Euclidean algorithm, you can use the totient function to determine the multiplicative inverse. For example, if <I>n</I> is a prime, then 0(<I>n</I>) = <I>n</I>-1. If <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>Then, the multiplicative inverse <I>x</I><SUP>-1</SUP> mod <I>n</I> becomes:</P>
<!-- CODE SNIP //-->
<PRE>
Inverse = x<SUP>0(n)-1</SUP> mod n
</PRE>
<!-- END CODE SNIP //-->
<P>To illustrate this, let’s assume you want to determine 5<SUP>-1</SUP> mod 3. Since 3 is prime, you would then compute:</P>
<!-- CODE SNIP //-->
<PRE>
multiplicative inverse = 5<SUP>0(3)-1</SUP> mod 3
</PRE>
<!-- END CODE SNIP //-->
<P>Because:
</P>
<!-- CODE SNIP //-->
<PRE>
0(3) = 3-1 = 2
</PRE>
<!-- END CODE SNIP //-->
<P>Then:
</P>
<!-- CODE SNIP //-->
<PRE>
multiplicative inverse = 5<SUP>2-1</SUP> mod 3 = 5 mod 3 = 2
</PRE>
<!-- END CODE SNIP //-->
<P>Check the preceding as follows:
</P>
<!-- CODE SNIP //-->
<PRE>
2*5 mod 3 = 10 mod 3 = 1
</PRE>
<!-- END CODE SNIP //-->
<P>Sure enough, 2 is the multiplicative inverse of 5 mod 3.
</P>
<P>Now that you have an appreciation for the general mathematics behind public key cryptology, let me turn your attention to the operation of a popular public key encryption system.</P><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="378-381.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="385-387.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
</body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -