Integer Algorithms In Cryptology And Information Assurance

Boris S Verkhovsky

• Publisher: WSPC
• Year: 2014
• eBook ISBN: 9789814623766
• Topic: Biological Sciences
• Subtopic: Science General
• Index: Biological Sciences

Integer Algorithms in Cryptology and Information Assurance is a collection of the author's own innovative approaches in algorithms and protocols for secret and reliable communication. It concentrates on the “ what ” and “ how ” behind implementing the proposed cryptographic algorithms rather than on formal proofs of “why” these algorithms work.

The book consists of five parts (in 28 chapters) and describes the author's research results in:

-->

• Innovative methods in cryptography (secret communication between initiated parties);
• Cryptanalysis (how to break the encryption algorithms based on computational complexity of integer factorization and discrete logarithm problems);
• How to provide a reliable transmission of information via unreliable communication channels and;
• How to exploit a synergetic effect that stems from combining the cryptographic and information assurance protocols.

-->

This text contains innovative cryptographic algorithms; computationally efficient algorithms for information assurance; new methods to solve the classical problem of integer factorization, which plays a key role in cryptanalysis; and numerous illustrative examples and tables that facilitate the understanding of the proposed algorithms.

The fundamental ideas contained within are not based on temporary advances in technology, which might become obsolete in several years. The problems addressed in the book have their own intrinsic computational complexities, and the ideas and methods described in the book will remain important for years to come.

Contents:

• Introductory Notes on Security and Reliability
• Enhanced Algorithm for Modular Multiplicative Inverse
• Multiplication of Large-Integers Based on Homogeneous Polynomials
• Deterministic Algorithms for Primitive Roots and Cyclic Groups with Mutual Generators
• Primality Testing via Complex Integers and Pythagorean Triplets
• Algorithm Generating Random Permutation
• Extractability of Square Roots and Divisibility Tests
• Extraction of Roots of Higher Order in Modular Arithmetic
• Public-Key Cryptography Based on Square Roots and Complex Modulus
• Cubic Roots of Complex Integers and Encryption with Digital Isotopes
• Exponentiation-Free Accelerated Encryption/Decryption Protocol
• Cryptocol Based on Three-Dimensional Elliptic Surface
• Multi-Parametric Cryptography for Rapid Transmission of Information
• Scheme for Digital Signature that Always Works
• Hybrid Cryptographic Protocols Providing Digital Signature
• Control Protocols Providing Information Assurance
• Information Assurance Based on Cubic Roots of Integers
• Simultaneous Information Assurance and Encryption Based on Quintic Roots
• Modular Equations and Integer Factorization
• Counting Points on Hyper-Elliptic Curves and Integer Factorization
• Integer Factorization via Constrained Discrete Logarithm Problem
• Decomposability of Discrete Logarithm Problems
• Detecting Intervals and Order of Point on Elliptic Curve
• Generalization of Gauss Theorem and Computation of Complex Primes
• Space Complexity of Algorithm for Modular Multiplicative Inverse
• New Algorithm Can Be Computed
• Search for Period of Odd Function
• Optimized Search for Maximum of Function on Large Intervals
• Topological Design of Satellite Communication Networks

Readership: Integer Algorithms in Cryptology and Information Assurance would be a book of interest for researchers and developers working on telecommunication security and/or reliability, in industries such as business and banking, national security agencies, militaries, interplanetary space exploration, and telemedicine. Faculty members in Computer Science, Electrical Engineering, Information Technology, Bio-Engineering and Applied Mathematics Departments, who are planning to teach advanced courses in cryptography; graduate and PhD students; advanced undergraduate students of the same fields; and various national cryptographic societies would also find this book useful.
Key Features:

• Innovative cryptographic algorithms
• Computationally efficient algorithms for information assurance
• New methods to solve the classical problem of integer factorization, which plays a key role in cryptanalysis
• Numerous illustrative examples and tables that facilitate understanding of the proposed algorithms
• The style of the book, which concentrates on constructive description of wha t and how to implement the proposed cryptographic algorithms rather than on formal proofs of why these algorithms work

Chapter 1

Enhanced Algorithm for Modular Multiplicative Inverse

1. Introduction: Division of Two Integers

As it was indicated above, output of division of two integers in most of the cases is not integer in traditional arithmetic. However, in modular arithmetic, (c/d) mod p is either integer if d and p are relatively prime, or it does not exist if d and p are not co-prime, i.e., if gcd(d, p) > 1. Analogous case exists in traditional arithmetic:

For instance, if dy = 1 and d = 0, then there is no unique y that satisfies 0y = 1.

In this chapter, we provide an Enhanced-Euclid algorithm (NEA) that finds for two relatively prime integers p₀ and p₁ an integer number x, satisfying the equation

This integer x is called a multiplicative inverse of p₁ modulo p₀ or, for short, a Modular Multiplicative Inverse (MMI). However, if p₀ and p₁ are not relatively prime, then the NEA finds a gcd(p₀, p₁). The Extended-Euclid algorithm (XEA) (Knuth, 1997) also finds a MMI of p₀ and p₁ if gcd(p₀, p₁) = 1. Otherwise, the XEA finds gcd(p₀, p₁).

In this chapter, we prove a validity of the NEA and provide its analysis. The analysis demonstrates that the NEA is faster than the XEA.

2. Basic Arrays and their Properties

Let us consider five finite integer arrays:

Definition 2.1. Let {p_i} and {c_i} be integer arrays defined according to the following generating rules:

given two relatively prime integers p₀ and p₁ such that p₀ > p₁,

Definition 2.2. Let for every k ≥ 1 {t_k} be an arbitrary array; let {w_k} and {z_k} be defined by the following generating rules: if w₀, w₁, z₀ and z₁ are initially specified,

Proposition 2.3. Let us consider a sequence of determinants

, then for every k ≥ 1,

Consider D_k and substitute in the left column the values of w_k and z_k defined in (2.3).

After simplifications, it follows that D_k = −D_k−1, then this relation, if applied telescopically, implies (2.4).

Proposition 2.4. Let all three arrays {t_k}, {w_k} and {z_k} be integer, and

w₀ := 1, z₀ := 0, |z₁| := 1.

Proposition 2.3 implies that for every w₁ (−1)^k−1z₁z_k is a multiplicative inverse of w_k−1 modulo w_k. Indeed, since D₁ = −z₁, then (2.4) implies that

w_kz_k−1 − z_kw_k−1 = (−1)^kz₁,

or that

Therefore, (2.5) implies that {w_k−1[(−1)^k−1 z₁z_k]−1}/w_k = (−1)^k−1z₁z_k−1, i.e., x = (−...

Table of contents

• Cover Page
• Title Page
• Copyright Page
• About the Author
• Dedication
• Preface
• Acknowledgments
• Contents
• 0. Introductory Notes on Security and Reliability
• 1. Enhanced Algorithm for Modular Multiplicative Inverse
• 2. Multiplication of Large-Integers Based on Homogeneous Polynomials
• 3. Deterministic Algorithms for Primitive Roots and Cyclic Groups with Mutual Generators
• 4. Primality Testing via Complex Integers and Pythagorean Triplets
• 5. Algorithm Generating Random Permutation
• 6. Extractability of Square Roots and Divisibility Tests
• 7. Extraction of Roots of Higher Order in Modular Arithmetic
• 8. Public-Key Cryptography Based on Square Roots and Complex Modulus
• 9. Cubic Roots of Complex Integers and Encryption with Digital Isotopes
• 10. Exponentiation-Free Accelerated Encryption/ Decryption Protocol
• 11. Cryptocol Based on Three-Dimensional Elliptic Surface
• 12. Multi-Parametric Cryptography for Rapid Transmission of Information
• 13. Scheme for Digital Signature that Always Works
• 14. Hybrid Cryptographic Protocols Providing Digital Signature
• 15. Control Protocols Providing Information Assurance
• 16. Information Assurance Based on Cubic Roots of Integers
• 17. Simultaneous Information Assurance and Encryption Based on Quintic Roots
• 18. Modular Equations and Integer Factorization
• 19. Counting Points on Hyper-Elliptic Curves and Integer Factorization
• 20. Integer Factorization via Constrained Discrete Logarithm Problem
• 21. Decomposability of Discrete Logarithm Problems
• 22. Detecting Intervals and Order of Point on Elliptic Curve
• 23. Generalization of Gauss Theorem and Computation of Complex Primes
• 24. Space Complexity of Algorithm for Modular Multiplicative Inverse
• 25. New Algorithm Can Be Computed
• 26. Search for Period of Odd Function
• 27. Optimized Search for Maximum of Function on Large Intervals
• 28. Topological Design of Satellite Communication Networks
• References