C与C++密码学实践：大数运算与模指数运算解析

需积分: 9 96 浏览量更新于2024-07-24 收藏 3.53MB PDF 举报

"Cryptography in C and Cpp 4th edition 是一本专注于密码学在C和C++语言中的应用的书籍，内容涵盖了大量的加密算法和技术。" 本书旨在深入探讨C和C++编程语言中的密码学基础和实践，通过清晰的英文文本向读者展示如何在这些语言中实现安全的加密算法。书中的内容包括了数学基础、数字表示法、接口语义、基本运算（如加减乘除）、模算术以及重要的指数运算等核心概念。 1. **介绍**: 本书的开篇介绍了密码学的基本概念，以及为何在C和C++中实现密码算法的重要性，为后续章节奠定了基础。 2. **数字格式与大数表示**: 这一章讲解了在C语言中如何表示和处理大数，这对于实现许多密码学算法至关重要，因为它们经常涉及超出标准整型范围的计算。 3. **接口语义**: 接口语义是编程中的关键部分，特别是在涉及低级别语言如C和C++时，理解函数调用和数据传递的细节对于正确实现密码算法至关重要。 4. **基本运算**: 书中详细讨论了加法、减法、乘法和除法的实现，包括不同的乘法算法，如格雷戈里-克拉姆算法（Grade School Method）、快速平方法以及卡塔诺比亚算法（Karatsuba Algorithm）。 5. **模算术与余数类计算**: 模算术是密码学中的重要工具，这一章解释了如何进行模运算以及如何利用余数类进行计算，这对于理解公钥密码系统如RSA的基础至关重要。 6. **模幂运算**: 本章详细阐述了模幂运算的不同方法，包括初等方法、M-ary exponentiation、加法链和窗口技术，以及蒙哥马利缩减和指数运算，这些都是高效实现如RSA加密和解密的关键。 6.5小节特别提到了指数运算在密码学中的应用，这通常涉及到公钥密码体制，如RSA和椭圆曲线密码学，其中指数运算的效率直接影响到系统的安全性与性能。该书对于希望深入了解密码学原理以及在C和C++中实现这些原理的开发者来说是一份宝贵的资源。它不仅涵盖了理论知识，还提供了实用的代码示例，帮助读者将理论应用于实际项目中。通过阅读本书，读者可以掌握创建安全通信和数据保护机制所需的技能。

Part I

Arithmetic and

Number Theory in C

How necessary arithmetic and the entire art of mathematics are can be easily

measured, in that nothing can be created that is not connected with precise

number and measurement, and no independent art can exist without its

measures and proportions.

—Adam Ries: Book of Calculation, 1574

Typographical rules for manipulating numerals are actually arithmetical

rules for operating on numbers.

—D. R. Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid

The human brain would no longer be burdened with anything that needed to

be calculated! Gifted people would again be able to think instead of scribbling

numbers.

—Sten Nadolny: The Discovery of Slowness, trans. Ralph Freedman

APress/Authoring/2005/04/10:10:11 Page 1

www.it-ebooks.info

CHAPTER 1

Introduction

God created the integers. All the rest is the work of man.

—Leopold Kronecker

If you look at zero you see nothing; but look through it and you will see the

world.

—Robert Kaplan, The Nothing That Is: A Natural History of Zero

TO BE INVOLVED WITH MODERN cryptography is to dive willy-nilly into number

theory, that is, the study of the natural numbers, one of the most beautiful areas

of mathematics. However, we have no intention of becoming deep-sea divers who

raise sunken treasure from the mathematical ocean ﬂoor, which in any case is

unnecessary for cryptographic applications. Our goals are much more modest.

On the other hand, there is no limit to the depth of involvement of number theory

with cryptography, and many signiﬁcant mathematicians have made important

contributions to this area.

The roots of number theory reach back to antiquity. The Pythagoreans—the

Greek mathematician and philosopher Pythagoras and his school—were already

deeply involved in the sixth century

B.C.E. with relations among the integers,

and they achieved signiﬁcant mathematical results, for example the famed

Pythagorean theorem, which is a part of every school child’s education. With

religious zeal they took the position that all numbers should be commensurate

with the natural numbers, and they found themselves on the horns of a serious

dilemma when they discovered the existence of “irrational” numbers such as

√

which cannot be expressed as the quotient of two integers. This discovery threw

the world view of the Pythagoreans into disarray, to the extent that they sought

to suppress knowledge of the irrational numbers, a futile form of behavior oft

repeated throughout human history.

Two of the oldest number-theoretic algorithms, which have been passed

down to us from the Greek mathematicians Euclid (third century

B.C.E.) and

Eratosthenes (276–195

B.C.E.), are closely related to the most contemporary

encryption algorithms that we use every day to secure communication across

the Internet. The “Euclidean algorithm” and the “sieve of Eratosthenes” are both

quite up-to-date for our work, and we shall discuss their theory and application

in Sections 10.1 and 10.5 of this book.

APress/Authoring/2005/04/10:10:11 Page 3

www.it-ebooks.info

Chapter 1

Among the most important founders of modern number theory are to be

counted Pierre de Fermat (1601–1665), Leonhard Euler (1707–1783), Adrien

Marie Legendre (1752–1833), Carl Friedrich Gauss (1777–1855), and Ernst Eduard

Kummer (1810–1893). Their work forms the basis for the modern development of

this area of mathematics and in particular the interesting application areas such as

cryptography, with its asymmetric procedures for encryption and the generation

of digital signatures (cf. Chapter 17). We could mention many more names of

important contributors to this ﬁeld, who continue to this day to be involved in

often dramatic developments in number theory, and to those interested in a

thrilling account of the history of number theory and its protagonists, I heartily

recommend the book Fermat’s Last Theorem, by Simon Singh.

Considering that already as children we learned counting as something to be

taken for granted and that we were readily convinced of such facts as that two

plus two equals four, we must turn to surprisingly abstract thought constructs

to derive the theoretical justiﬁcation for such assertions. For example, set theory

allows us to derive the existence and arithmetic of the natural numbers from

(almost) nothing. This “almost nothing” is the empty (or null) set

∅ := {},

that is, the set that has no elements. If we consider the empty set to correspond

to the number

0, then we are able to construct additional sets as follows. The

successor

of 0 is associated with the set 0

:= {0 } = {∅ }, which contains

a single element, namely the null set. We give the successor of

0 the name 1,and

for this set as well we can determine a successor, namely

:= {∅, {∅ }}.

The successor of

1, which contains 0 and 1 as its elements, is given the name 2.

The sets thus constructed, which we have rashly given the names

0, 1, and 2,we

identify—not surprisingly—with the well-known natural numbers

0, 1,and2.

This principle of construction, which to every number

x associates a

successor

:= x ∪{x } by adjoining x to the previous set, can be continued to

produce additional numbers. Each number thus constructed, with the exception

0, is itself a set whose elements constitute its predecessors. Only 0 has no

predecessor. To ensure that this process continues ad inﬁnitum, set theory

formulates a special rule, called the axiom of inﬁnity: There exists a set that

contains

0 as well as the successor of every element that it contains.

From this postulated existence of (at least) one so-called successor set, which,

beginning with

0, contains all successors, set theory derives the existence of a

minimal successor set

N, which is itself a subset of every successor set. This

minimal and thus uniquely determined successor set

N is called the set of natural

numbers, in which we expressly include zero as an element.

It was not decisive for this choice that according to standard DIN 5473 zero belongs to the

natural numbers. From the point of view of computer science, however, it is practical to begin

counting at zero instead of 1, which is indicative of the important role played by zero as the

neutral element for addition (additive identity).

APress/Authoring/2005/04/10:10:11 Page 4

www.it-ebooks.info

Introduction

The natural numbers can be characterized by means of the axioms of

Giuseppe Peano (1858–1932), which coincide with our intuitive understanding of

the natural numbers:

(I) The successors of two unequal natural numbers are unequal: From

n = m

it follows that n

= m

,foralln, m ∈ N.

(II) Every natural number, with the exception of

0, has a predecessor:

= N \{0 }.

(III) The principle of complete induction: If

S ⊂ N, 0 ∈ S,andn ∈ S always

imply

∈ S,thenS = N.

The principle of complete induction makes it possible to derive the arithmetic

operations with natural numbers in which we are interested. The fundamental

operations of addition and multiplication can be deﬁned recursively as follows.

We begin with addition:

For every natural number

n ∈ N there exists a function s

from N to N such

that

(i)

(0) = n,

(ii)





=(s

(x))

for all natural numbers x ∈ N.

The value of the function

(x) is called the sum n + x of n and x.

The existence of such functions

for all natural numbers n ∈ N must,

however, be proved, since the inﬁnitude of natural numbers does not a priori

justify such an assumption. The existence proof goes back to the principle of

complete induction, corresponding to Peano’s third axiom above (see [Halm],

Chapters 11–13). For multiplication one proceeds analogously:

For every natural number

n ∈ N there exists a function p

from N to N such

that

(i)

(0)=0,

(ii)





= p

(x)+n for all natural numbers x ∈ N.

The value of the function

(x) is called the product n · x of n and x.

As expected, multiplication is deﬁned in terms of addition. For the arithmetic

operations thus deﬁned one can prove, through repeated application of complete

induction on

x in accordance with Axiom III, such well-known arithmetic laws as

associativity, commutativity, and distributivity (cf. [Halm], Chapter 13). Although

we usually use these laws without further ado, we shall help ourselves to them as

much as we please in testing our FLINT functions (see Chapters 13 and 18).

In a similar way we obtain a deﬁnition of exponentiation, which we give here

in view of the importance of this operation in what follows.

APress/Authoring/2005/04/10:10:11 Page 5

www.it-ebooks.info

剩余481页未读，继续阅读

mnb123jhg

粉丝: 4
资源: 13

C与C++密码学实践：大数运算与模指数运算解析

Cryptography and Network Security, 5th Edition

Cryptography And Network Security, 4Th Edition

Cryptography in C and C++, Second Edition （With Source Code）

GROUP THEORY IN CRYPTOGRAPHY

java cryptography: tools and techniques

cryptographydeprecationwarning: python 3.6 is no longer supported by the python core team. therefore, support for it is deprecated in cryptography and will be removed in a future release. from cryptography.hazmat.backends import default_backend

《New Directions in Cryptography》的引用格式

RuntimeError: 'cryptography' package is required for sha256_password or caching_sha2_password auth methods

最新资源