DEV Community: Prince Justice Sena Essiel

Zero Knowledge Proofs Series #7 [Diffie-Hellman Key Exchange , Elliptic Curves II]

Prince Justice Sena Essiel — Thu, 28 Mar 2024 02:07:43 +0000

Exploring Cryptographic Functions: From Graphs to Elliptic Curves

Understanding the mathematical functions that describe graphs is crucial for cryptography. From linear to quadratic to polynomial functions, each offers unique characteristics that impact their suitability for encryption algorithms.

Linear Functions

A linear function is the simplest form of a graph, described by the equation ( y = mx + c ), where ( m ) represents the slope and ( c ) represents the y-intercept. Linear functions produce straight lines on a graph.

Consider the linear function:

[ y = 2x + 1 ]

This function satisfies the points:

( x )	( y )
-1	-1
0	1
1	3

Quadratic Functions

Quadratic functions introduce a U-shaped curve to the graph, described by the equation ( y = ax^2 + bx + c ).

Consider the quadratic function:

[ y = x^2 - x + 2 ]

This function satisfies the points:

( x )	( y )
-1	4
0	2
1	2

Polynomial Functions

Polynomial functions provide curves with various shapes and degrees, offering higher complexity and flexibility. They are described by equations like ( y = a_nx^n + ... + a_1x + a_0 ).

Consider the polynomial function:

[ y = x^3 - x^2 + x - 1 ]

This function satisfies the points:

( x )	( y )
-1	-4
0	-1
1	1

Transition to Elliptic Curve Cryptography (ECC)

While polynomial functions provide increased complexity and flexibility, they still have limitations for certain cryptographic applications. This is where elliptic curve cryptography (ECC) steps in.

Elliptic Curve Cryptography Fundamentals

Elliptic curve cryptography operates on points of an elliptic curve defined over a finite field. Key operations in ECC include:

Point Addition: Combining two points on the curve to find a third point that lies on the curve.
Scalar Multiplication: Repeatedly adding a point to itself by a scalar value.
Infinity Point: The point at infinity serves as the identity element for point addition.
Base Point: A fixed point on the curve used as a reference for scalar multiplication.

For a visual understanding of these operations, you can watch https://www.youtube.com/watch?v=XmygBPb7DPM

Turning Classical Cryptosystems into Elliptic Curve Versions

Exploring Secure Key Exchange: Diffie-Hellman and Elliptic Curve Diffie-Hellman

In the realm of secure communication, one of the fundamental challenges is how to exchange cryptographic keys over an insecure channel without the risk of interception. This challenge is elegantly addressed by two widely used protocols: Diffie-Hellman key exchange (DHE) and its elliptic curve counterpart, Elliptic Curve Diffie-Hellman (ECDH). In this blog post, we delve into the inner workings of these protocols, shedding light on their mechanisms and the security they provide.

Understanding Diffie-Hellman Key Exchange

Setup:

Alice and Bob agree on a large prime number ( p ) and a base ( G ) (generator) in a finite field.

Key Generation:

Alice chooses a private key ( a ) and computes her public key ( G^a ).
Similarly, Bob chooses a private key ( b ) and computes his public key ( G^b ).

Key Exchange:

Alice sends her public key ( G^a ) to Bob, and Bob sends his public key ( G^b ) to Alice.

Shared Secret:

Alice computes ( (G^b)^a = (G^a)^b ) and Bob computes ( (G^a)^b = (G^b)^a ).
Now, both Alice and Bob possess the same shared secret ( G^{ab} ), which can be used for secure communication.

The Beauty of Elliptic Curve Diffie-Hellman

While DHE operates in a finite field, ECDH operates on points of an elliptic curve, providing equivalent security with smaller key sizes. The principles are similar, but the operations are performed on elliptic curve points.

Setup:

Alice and Bob agree on an elliptic curve and a base point ( P ) on that curve.

Key Generation:

Alice chooses a private key ( a ) and computes her public key ( aP ).
Bob chooses a private key ( b ) and computes his public key ( bP ).

Key Exchange:

Alice sends her public key ( aP ) to Bob, and Bob sends his public key ( bP ) to Alice.

Shared Secret:

Alice computes ( (bP)^a = a(bP) ).
Bob computes ( (aP)^b = b(aP) ).
They both arrive at the same shared secret ( abP ) without explicitly exchanging it over the network.

Elgamal Crypto System

Setup:

Alice and Bob agree on a large prime number ( p ) and a base ( G ) (generator) in a finite field.

Bob's Encryption:

Bob generates a random ephemeral key ( k ). He computes ( G^k ) and sends it to Alice along with the ciphertext ( C = M \times (G^a)^k ).

Alice's Decryption:

Alice receives ( G^k ) and ( C ).
She computes the shared secret ( S = (G^k)^a = G^{ka} ) using her private key ( a ).
She calculates the multiplicative inverse of ( S ) to obtain ( (S^{-1}) = (G^{ka})^{-1} = (G^a)^{-k} ).
Alice then decrypts the ciphertext ( C ) by computing ( M = C \times (S^{-1}) ).

Now, let's address your question about how the decryption process works:

[ M = C \times (S^{-1}) ]

Substituting ( C = M \times (G^a)^k ):

[ M = (M \times (G^a)^k) \times (S^{-1}) ]

Since ( (G^a)^k = G^{ka} ):

[ M = M \times G^{ka} \times (G^{ka})^{-1} ]

Multiplicative inverses cancel out:

[ M = M ]

So, when Alice decrypts the ciphertext using her private key ( a ), she effectively cancels out the effect of the ephemeral key ( k ), leaving her with the original message ( M ). This process ensures that only Alice, possessing the private key ( a ), can decrypt the message successfully, even if an eavesdropper intercepts the communication.

Transition to Elliptic Curve ElGamal

Setup:

Alice and Bob agree on an elliptic curve and a base point ( P ) on that curve.

Key Generation:

Alice chooses a private key ( a ) and computes her public key ( aP ).
Bob chooses a private key ( b ) and computes his public key ( bP ).

Shared Secret:

Alice computes ( abP = (bP)^a ).
Bob computes ( abP = (aP)^b ).
They both arrive at the same shared secret ( abP ) without explicitly exchanging it over the network.

Message from Bob

Bob's Encryption:

Bob generates a random ephemeral key ( k ). He computes ( kP ) and sends it to Alice along with the ciphertext ( C = M + (aP)k ). Alice's Decryption:
Alice receives ( kP ) and ( C ).

The description provided seems to describe a combination of both the Diffie-Hellman key exchange and the ElGamal encryption scheme.

Here's a breakdown of the elements mentioned:

Key Exchange:

The initial part about Alice and Bob exchanging public keys (( G^a ) and ( G^b )), and computing the shared secret (( G^{ab} )), corresponds to the Diffie-Hellman key exchange.

Encryption:

The later part about Bob encrypting a message (( M )) using an ephemeral key (( k )) and the public key of Alice (( (aP) )), (( M + (aP)k )), corresponds to the ElGamal encryption scheme.

So, to clarify, the process described involves:

Key Exchange: Diffie-Hellman
Encryption: ElGamal

Both schemes are fundamental cryptographic techniques used for different purposes. Diffie-Hellman is primarily used for key exchange, while ElGamal is a public-key cryptosystem used for encryption and digital signatures.

Conclusion

Understanding the foundational principles of graph functions and their role in cryptography provides insights into designing secure communication systems. From linear to polynomial functions, each offers unique characteristics that impact encryption algorithms. Transitioning to elliptic curve cryptography further enhances security and efficiency, making it a preferred choice for modern cryptographic applications. By exploring these concepts, we can build robust systems that safeguard sensitive information in an increasingly connected digital world.

Zero Knowledge Proofs Series #6 [Cryptographic Key Exchanges & Elliptic Curves I ]

Prince Justice Sena Essiel — Mon, 18 Mar 2024 20:29:06 +0000

History of Cryptography and its Relation to Today -"The past is the key to the future - Unknown"

Cryptography, the art of protecting information, boasts a long and fascinating history. This breakdown explores its evolution, focusing on the shift from symmetric to asymmetric methods and the importance of key exchange.

Early Ciphers

1700 BC: Egyptians utilized Hieroglyphics: https://en.wikipedia.org/wiki/Egyptian_hieroglyphs - a writing system for inscriptions on walls, tombs, and more. While not a true cipher, it offered obscurity to those unfamiliar with the system.
50 BC: Julius Caesar employed a simpler method - the Caesar cipher: https://dev.to/anasnmu/caesar-cipher-and-javascript-1kl1. This involved shifting letters by a fixed number of positions.
16th Century: The Vigenère cipher emerged, offering more sophistication. It used a keyword to determine the shift value for each letter, creating a more complex pattern compared to the Caesar cipher.
World War II: The Enigma machine, used by Nazi Germany, was an electro-mechanical marvel that employed rotors and plugboards for complex encryption. Breaking Enigma provided crucial intelligence to the Allies.

A Comparison of Ciphers

Cipher	Description	Strengths	Weaknesses	Historical Context
Caesar Cipher	Shifts plaintext letters by a fixed number of positions.	Simple to implement.	Extremely weak, vulnerable to frequency analysis.	Used by Julius Caesar and throughout history for simple communication.
Vigenère Cipher	Uses a keyword to determine the shift value for each letter.	More secure than Caesar cipher due to varying shifts.	Vulnerable to frequency analysis of long texts and statistical techniques to identify keyword patterns.	Developed around the 16th century.
Enigma Machine (WWII)	Electro-mechanical cipher device with complex encryption.	Highly complex and dynamic, initially very difficult to crack.	Relied on predictable elements like rotor settings, which were eventually exploited.	Used by Nazi Germany during World War II.
Egyptian Hieroglyphs	A writing system using pictures (hieroglyphs) to represent words or sounds.	Visually appealing, offering some obscurity to those unfamiliar with the system.	Not a true cipher, but can be used for limited secret communication. Deciphering requires knowledge of the language and hieroglyphic meanings.	Developed around 3200 BC.

Note: All the ciphers mentioned above are symmetric in nature. This means for nearly 4,000 years, cryptography functioned in a similar way.

The Rise of Asymmetric Cryptography

In 1975, the first form of asymmetric cryptography was created. This revolutionary approach utilizes a key pair:

Public Key (Pb): Known to everyone, similar to a mailbox address.
Private Key (Pb): Kept secret, like a key to open the mailbox.

Information encrypted with the public key can only be decrypted with the corresponding private key, eliminating the need for secure key distribution.

Examples of Key Exchange with Asymmetric Cryptography

Secure Email: When you send an encrypted email, you use the recipient's public key to encrypt the message. Only their private key can decrypt it, ensuring confidentiality.
HTTPS: Secure websites (indicated by the padlock symbol and "https" in the address bar) establish secure connections using asymmetric cryptography. The website's public key encrypts communication, and your browser uses trusted certificates to verify its authenticity.

Symmetric key cryptography offers efficient bulk encryption, while asymmetric cryptography allows for secure key exchange and digital signatures. We still use both methods today.

Exploring Terminology: Symmetric vs. Asymmetric Cryptography

Scenario: Imagine Alice has a secret message (X) for Bob, and Beatrice is eavesdropping.

Symmetric Encryption:

Choose a Shift Value: Decide on the number of positions to shift letters (e.g., 3 positions).
Encryption: Find the plain text letter on the inner circle (Plaintext Alphabet) and look at the corresponding letter on the outer circle (Ciphertext Alphabet) for the encrypted letter.

Example message: "HELLO" becomes "LHORO" with a shift value of 3.

3.Decryption: Reverse the process using the same shift value to return to the original message.

Choose a Shift Value: This is the number of positions you'll move each letter. In our example, let's use a shift value of 3.
Encrypting a Message: Find the plain text letter on the inner circle (Plaintext Alphabet). Look at the corresponding letter on the outer circle (Ciphertext Alphabet) - that's your encrypted letter!
For instance, if your message is "HELLO", follow these steps:
H -> L (Move 3 positions to the right)
E -> H
L -> O
L -> O
O -> R
The encrypted message becomes "LHORO".
Decoding a Message:
The decryption process is simply the reverse. Use the same shift value but move in the opposite direction on the Caesar Cipher disc. So, to decode "LHORO" with a shift value of 3:
L -> H (Move 3 positions to the left)
H -> E
O -> L
R -> L
O -> O
This gets you back to the original message "HELLO".

Asymmetric Encryption (Continued)

Public Key (Pb) and Private Key (Pb):

Public Key (Pb): This key is available to everyone, including Alice, Beatrice, and even Eve. It's like the mailbox address – anyone can find it.
Private Key (Pb): This key is like a secret key to open the mailbox – only Bob keeps it safe. No one else has access to it.

Sending the Love Notes

Alice Encrypts Her Message: Alice gets hold of Bob's public key (Pb). She uses this key like a special lock to encrypt her message (X) with a complex mathematical algorithm. This transforms her message into an unreadable format, like a love note written in a secret code (Ciphertext, C).
- Importantly, only Bob's private key can decrypt messages encrypted with his public key. Even if Eve intercepts the encrypted message (C), she cannot decipher it without Bob's private key.
Sending the Encrypted Note: Alice discreetly sends the encrypted message (Ciphertext, C) to Bob.
Beatrice Does the Same: Beatrice follows Alice's lead. She also gets Bob's public key (Pb) and encrypts her message (Y) for Bob using the same encryption process. She sends her encrypted love note (Ciphertext, D) to Bob as well.

Bob Reads the Secret Messages

Decrypting the Notes: Bob, the lucky recipient, receives the encrypted messages (Ciphertext, C and D) from Alice and Beatrice. He uses his own private key (Pb), like the secret key to his mailbox, to decrypt each message.
Revealing the Secrets: The decryption process unlocks the true messages (X and Y) from Alice and Beatrice. Now Bob can finally read their heartfelt confessions!

The Power of Asymmetry

Secure Communication: Asymmetric cryptography ensures that only Bob, with his private key, can decrypt the messages encrypted with his public key. This keeps the messages confidential, even if Eve intercepts them.
No Risky Key Sharing: Unlike traditional methods where a shared key needs to be distributed securely, here Bob's public key can be shared freely. Only his private key can unlock the messages.

Future Exploration

In the next part, we'll delve into:

Elliptic Curve Cryptography (ECC): Explore the math behind this efficient and secure asymmetric cryptography method.
Different Forms for Elliptic Curves for the right use-cases

This concludes the basic explanation of cryptography. As you can see, cryptography plays a vital role in protecting information in our digital age. By understanding its evolution and different methods, we can appreciate its significance and use it responsibly.

ZKP Series #5 [ Discrete Logarithm ]

Prince Justice Sena Essiel — Thu, 14 Mar 2024 02:25:33 +0000

We are going think of Discrete LogarImagine a world of secure communication, where confidential messages are scrambled and only authorized individuals can access them. This is the realm of cryptography, and a crucial concept within it is the Discrete Logarithm Problem (DLP).

Let's delve into the world of DLP through the lens of data and graphs, without getting sidetracked by war games.

Setting the Stage:

Prime Modulus: A large prime number acts as a foundation for the encryption process. Think of it as a giant vault door with a complex lock (e.g., a prime number like 59).
Generator: A publicly known number that serves as a key ingredient in the encryption recipe (e.g., a number like 2).
The Data: A Glimpse into the Encryption Process

The provided table offers a snippet of the relationship between exponents and their modular results:

Mod 59	(2^x \mod 59)	(2^x)	(2^x \mod 59)
0	1	1	1
1	2	2	2
2	4	4	4
3	8	8	8
4	16	16	16
5	32	32	32
6	5	64	5
7	10	128	10
8	20	256	20
9	40	512	40
10	21	1024	21
11	42	2048	42
12	23	4096	23
13	46	8192	46
14	31	16384	31
15	3	32768	3
16	6	65536	6
17	12	131072	12
18	24	262144	24
19	48	524288	48
20	37	1048576	37
21	19	2097152	19
22	38	4194304	38
23	41	8388608	41
24	35	16777216	35
25	17	33554432	17
26	34	67108864	34
27	7	134217728	7
28	14	268435456	14
29	28	536870912	28
30	56	1073741824	56
31	55	2147483648	55
32	53	4294967296	53
33	49	8589934592	49
34	41	17179869184	41
35	35	34359738368	35
36	17	68719476736	17
37	34	137438953472	34
38	7	274877906944	7
39	14	549755813888	14
40	28	1099511627776	28
41	56	2199023255552	56
42	55	4398046511104	55
43	53	8796093022208	53
44	49	17592186044416	49
45	41	35184372088832	41
46	35	70368744177664	35
47	17	140737488355328	17
48	34	281474976710656	34
49	7	562949953421312	7
50	14	1125899906842624	14
51	28	2251799813685248	28
52	56	4503599627370496	56
53	55	9007199254740992	55
54	53	18014398509481984	53
55	49	36028797018963968	49
56	41	72057594037927936	41
57	35	144115188075855872	35
58	17	288230376151711744	17

Here's what the data signifies:

Mod 59: This column represents the remainder obtained after dividing the result of raising 2 to the power of x by 59.
(2^x mod 59): This column shows the outcome of calculating 2 raised to the power of x and then taking the remainder when divided by 59.
Visualizing the Challenge: The Power of Graphs

Imagine a graph where the x-axis represents the exponent (x) and the y-axis represents the value of 2^x \mod 59. While the specific graph you mentioned isn't directly included, here's a general understanding:

Cyclical Nature: As you move along the x-axis (increasing the exponent), the corresponding y-values exhibit a repeating pattern. This recurrence arises due to the modular operation (division by the prime modulus).
Challenges for Codebreakers: Certain exponent values lead to the same remainder after division by the prime modulus. This cyclical behavior makes it incredibly difficult to determine the exact exponent used in the encryption process solely based on the encrypted message.
The Intricacy of DLP:

The DLP hinges on the following aspects:

Vast Number of Possibilities: With a large prime modulus like 59, there exist numerous possible exponents that could have resulted in the same encrypted message. Imagine searching for a specific grain of sand on a massive beach – the sheer number of options makes brute-force guessing nearly impossible.
One-Way Trapdoor: Raising a base (like 2) to different powers modulo a prime modulus is relatively simple. However, reversing this process to find the specific exponent used (akin to finding the grain of sand) is computationally infeasible due to the vast number of possibilities and the cyclical nature.
In essence, the DLP acts like a one-way door:

Information can easily flow in one direction (encryption).
Retrieving the original information from the encrypted message (decryption) without the secret key (the exponent) is exceptionally challenging.
Real-World Applications:

The DLP underpins various cryptographic systems:

Secure Communication: Protects online transactions, communication channels, and digital signatures.
Password Management: Enables secure storage and verification of passwords on various platforms.
Blockchain Technology: Plays a vital role in securing transactions within blockchain networks.
Conclusion:

The data and graphs offer a simplified glimpse into the fascinating world of the DLP. In real-world cryptography, much larger prime numbers and more intricate mathematical operations are employed to ensure the near impossibility of cracking the code. This makes the DLP a cornerstone of secure communication in our digital age.

Disclaimer: This explanation focuses on a simplified example. Real-world cryptography involves complex mathematical concepts and sophisticated algorithms.

ZK Series #4 [ Sets, Groups, Rings , Finite Fields and Prime Fields]

Prince Justice Sena Essiel — Wed, 13 Mar 2024 00:38:12 +0000

In Series #3 we spoke about Modular Arithmetic and there were some statements that I made that had no backing. I intend to use this part to give the whole picture and link things up.

Set Theory

I am sure from Elementary School we all learn about sets but a quick reminder is think of a group of items that are related. If I ask you to name the top 10 richest people in the world, the list you enumerated creates a set. In math, we call it a set of people of the top 10 richest people.

We are going to lay some foundational concepts by getting some Set Theory vocabulary; Our new words are

Set Equality: Sets are equal if they contain the same elements, regardless of the order.
- For example, the sets {1, 2, 3} and {3, 2, 1} are considered equal because they contain the same elements.
Cardinality: This refers to the number of elements in a set.
Super Set: A set that contains all the elements of another set, possibly with additional elements.
Subset: A set whose elements are all contained within another set.

I would like to talk about the properties of number systems because we are going to be defining key terms based on this foundational principle

Property	Explanation
Commutative	The order of operands can be swapped without changing the result.
	For addition: (a + b = b + a)
	For multiplication: (a \times b = b \times a)
Closure	When you perform an operation on two elements, the result is always another element of the same type.
	For addition: Adding any two whole numbers gives you another whole number.
	For multiplication: Multiplying any two real numbers gives you another real number.
Associative	The grouping of operations doesn't affect the result.
	For addition: ((a + b) + c = a + (b + c))
	For multiplication: ((a \times b) \times c = a \times (b \times c))
Identity	There exists a special element called the identity element, which leaves other elements unchanged when combined.
	For addition: The identity element is 0, because (a + 0 = a) for any (a).
	For multiplication: The identity element is 1, because (a \times 1 = a) for any (a).
Distributive	Describes how multiplication interacts with addition.
	For integers: (a \times (b + c) = (a \times b) + (a \times c))
	For real numbers: (a \times (b + c) = (a \times b) + (a \times c))

Group

Closure: Imagine you have a box of colorful marbles. Each marble has a number on it. When you pick any two marbles from the box and add them together, you always get another marble from the same box. For instance, if you have a blue marble with the number 3 and a red marble with the number 5, and you add them together, you'll get a purple marble with the number 8. That's closure!

In Math Lingo: A={0, 1,2,3, 4,5} a + b = c and c is a member of A so if we take 2 + 3 = 5 ; 5 is a memeber of A so that is closure

Associativity: Think of three numbered blocks, labeled A, B, and C. You want to stack them on top of each other. It doesn't matter if you first stack A on B and then C on top, or if you first stack B on C and then A on top. Either way, you'll end up with the same tower of blocks. That's associativity!

Inverse: Now, imagine you have a special block called the "magic zero block." When you combine this block with any other block, you get back the same block you started with. For example, if you have a green block with the number 7 and its magic zero block, when you put them together, you get the green block with the number 7 again. That's the inverse property!

Identity: Lastly, let's talk about the "superhero" block. This block doesn't change anything when you combine it with other blocks. So, if you have a yellow block with the number 10 and you add it to the superhero block, you'll still end up with the yellow block with the number 10. It's like the superhero block keeps everything in order!

So, in your box of colorful marbles, you have closure because adding any two marbles gives you another marble from the same box. You have associativity because the order in which you stack the blocks doesn't matter. You have inverses because every block has a magic zero block that returns the original block. And finally, you have the superhero block, which keeps everything stable and unchanged. That's the magic of your block group

Examples of Groups: In terms of the binary operators, addition is commonly used so the examples here are with respect to the addition binary operators

Integers (Z) under addition
:
Closure: 3 + 5 = 8; Associativity: (2 + 3) + 4 = 2 + (3 + 4); Identity: 0 (a + 0 = a); Inverse: -5 is the inverse of 5 (5 + (-5) = 0).
Real Numbers (R) under addition: Similar properties hold for addition of real numbers.
Non-zero rational numbers (Q \ {0}) under multiplication: Closure: (2/3) * (3/4) = 1/2; Associativity: (2 * 3) * 4 = 2 * (3 * 4); Identity: 1 (a * 1 = a); Inverse: Every non-zero rational number has a multiplicative inverse (a * a^-1 = 1).

_The set of Natural Numbers with the binary operator being addition does not fall into a group _

Abelian Group: An abelian group is one where the operation (usually addition) is commutative.

Rings

Rings extend groups by introducing a second binary operation (often multiplication) alongside the existing operation (usually addition). Rings satisfy the following properties:

Ring Properties: Inherit all group properties (closure, associativity, identity, and inverse for addition).

Distributive Property: The interaction between the two operations is defined. (a \times (b + c) = (a \times b) + (a \times c)).

Examples of rings

The set of integers (Z)
The set of Real Numbers(R)
The set of Complex Numbers (C)

In Multiplication 1 is the identity element because if we multiply any number by 1 we get the same number.

Matrices are not an example of Rings. If I have a set of 2x3 matrices we cannot multiply them.
**

(2x3) * (2*3) is impossible in matrices
(2x3) * (3*2) this is what we need and since 3 by 2 matrices is not a part of the set we cannot have Matrices being an example of a Ring

Field

A Field is a set on which addition, subtraction , multiplication and division are defined

Addition
Additive Inverse

-Multiplication

-Multiplicative Inverse for every number that is not zero

Consider the set of rational numbers (a/b) where a and b are integers and b is not equal to 0 .

They are commutative with addition
They are commutative with multiplication
All elements have a multiplicative inverse

Sets of integers do not form a field eg: we take a number 4 ; its multiplicative inverse is 1/4

set of 2x2 matrices do not form a field

But remember last time we spoke about the problems with infinite forms of sets in the normal number system and how we need finite set of numbers; now we want to apply that here

Perform mod 2 on any integer

Integer	Mod 2 Arithmetic
0	0
1	1
2	0
3	1
4	0
5	1
...	...

If we continue, we observe that the results of modulo 2 arithmetic alternate between 0 and 1, indicating that our new number system consists of just two elements: {0, 1}.

Performing mod 5 arithmetic on any integer yields the following pattern:

Integer	Mod 5 Arithmetic
0	0
1	1
2	2
3	3
4	4
5	0
6	1
7	2
8	3
9	4
10	0
11	1
...	...

Thus, we can conclude that the set of integers modulo 5 consists of the numbers {0, 1, 2, 3, 4}.

Classification

Now, let's classify whether Z mod 2 is a Group, Ring, or Field:

Addition

We expect the solution to be part of the set of integers mod 2, {0, 1}.
- Example: (3 \mod 2 + 4 \mod 2 = 1)
- Example: (5 \mod 2 + 10 \mod 2 = 0)
- This demonstrates closure, as the output is within our set.

Multiplication

Again, we expect the solution to be part of the set of integers mod 2, {0, 1}.
- Example: ((3 \mod 2) \times (4 \mod 2) = 3 \times 4 \mod 2 = 12 \mod 2 = 0)
- Example: ((5 \mod 2) \times (10 \mod 2) = 5 \times 10 \mod 2 = 50 \mod 2 = 0)
- This also shows closure.

Conclusion

As every element has a multiplicative inverse (1's inverse is always 1), {0, 1} forms a finite field.
Finite fields are also called Galois Fields (GF).
Z mod 2 is represented as GF(2).
Finite fields exist only in the form P^m, where P is a prime number and m is a positive integer.
- Example: GF(3^4) = GF(81)
If m > 1, it's called an extension field, such as GF(p^m).

This classification helps us understand the properties and structures of different mathematical systems.

In the next series we would talk more touch the surface of Elliptic Curve Cryptography

ZKP Series #3 [Finite fields & Modular Arithmetic ]

Prince Justice Sena Essiel — Mon, 11 Mar 2024 20:53:15 +0000

Computers have a history of finding it difficult to handle floating point numbers ; in simple terms, decimals but more so infinite decimals

If this is difficult to visualize you are not alone I am a visual learner so I have placed

const a = 10/3

const decimal_resultant = a.toFixed(50)
console.log(decimal_resultant);

#Click the link below and please copy and paste the code  here to see the results of this fraction or decimal

https://www.tutorialspoint.com/execute_nodejs_online.php

This was the value we got from doing the fraction operation 3.333333333333333481363069950020872056484222412109375000000000.

In short, we get re-occurring 3's after the .(dot) and then we get some random numbers and give up with zeros

This means we lose some precision with such numbers.

The Number System.

With the precision issue in mind, we need to understand the number system.

Understanding the Number System
To tackle this precision issue, we must delve into the underlying number system. Here's a breakdown:

Natural Numbers (ℕ): These are the counting numbers, starting from 1 and continuing indefinitely. While some include zero in this set, others exclude it.

Integers (ℤ): The set of all whole numbers, including both positive and negative integers.

Rational Numbers (ℚ): Any number that can be expressed as the quotient or fraction of two integers, where the denominator is not zero.

Real Numbers (ℝ): This encompasses all rational and irrational numbers, essentially covering the entire number line.

Complex Numbers (ℂ): This set includes numbers in the form of a + bi, where "a" and "b" are real numbers, and "i" represents the imaginary unit.

These number systems especially when used in cryptography cause issues due to computer architecture. We are going to borrow its some properties like arithmetic operations

Addition: 6 + 30 = 36
Substraction: 90 - 30 = 60
Multiplcation :

Division : 10/3 = .. our problem 3.333333333333333481363069950020872056484222412109375000000000.
what is zero = any number added to zero would give the same number that is zero n+0 =n

what are negatives = n+(-n) = 0

underlaying that issue and see if we can create a solution.

We need a number system that is

Would be primary based on whole numbers eg: 0, 1, 2, 3, 5,....
Only limited number of whole numbers [finite not infinite]
Be able to add all arithmetic operations you can do with our known number system eg of arithmetic operations include multiplication, addition , subtraction, division , exponentials..

Modulo Arithemetic

In the realm of modulo arithmetic, where numbers wrap around like a circular clock face, understanding addition and subtraction is essential for navigating numerical progression. Let's delve into modulo addition and subtraction through illustrative examples.

Modulo Addition

Example 1: Modulo Addition (Mod 12)

Let's visualize the expression 8 + 5 (mod 12):

Modulo Addition Example 1

We begin at the number 8 and proceed five steps clockwise on the modulo clock. As we reach 12, the sequence wraps around, resulting in the sum 1 (8 + 5 ≡ 1 mod 12).

Example 2: Modulo Addition (Mod 7)

Now, let's explore 4 + 6 (mod 7):

Modulo Addition Example 2

Following the same principle, we advance four steps from 4 on the modulo clock. The outcome, 3 (4 + 6 ≡ 3 mod 7), showcases the cyclical nature of modulo addition within our finite integer set.

Modulo Subtraction/ Additive Inverse

Example 1: Modulo Subtraction (Mod 12)

Consider the expression 3 - 9 (mod 12):

Modulo Subtraction Example 1

To calculate negative modulo, we use the formula: -a mod b = b - (a mod b).
For -6 mod 12:

First, we find 6 mod 12, which equals 6.
Then, we apply the formula: -6 mod 12 = 12 - (6 mod 12) = 12 - 6 = 6.

** Example 2: Modulo Subtraction (Mod 7)**

Let's navigate 6 - 4 (mod 7):

Modulo Subtraction Example 2

Starting at 6, we backtrack four steps counterclockwise on the modulo clock. The result, 2 (6 - 4 ≡ 2 mod 7), illustrates the reverse traversal characteristic of modulo subtraction within our finite integer set.

Through these examples, we gain insights into the dynamics of modulo arithmetic, paving the way for a deeper understanding of numerical progression and computational algorithms.

Multiplication with Modular Arithmetic:

Example: Multiplication with Modulo (Mod 12)

Multiplication is consecutive addition

Consider the expression 3 * 4 (mod 12):

Modulo Multiplication Example

We multiply 3 by 4 and then find the remainder when divided by 12. The result, 0 (3 * 4 ≡ 0 mod 12), showcases the structured nature of modulo multiplication within our finite integer set.

The Multiplicative Identity

Within modulo arithmetic, the number 1 serves as the multiplicative identity, anchoring numerical operations with unity and stability.

Example: Multiplicative Identity (Mod 7)

Let's examine the expression 5 * 1 (mod 7):

Multiplicative Identity Example link_to_image_6

Multiplying any number by 1 within the modulo 7 system retains the original value, illustrating the fundamental role of the multiplicative identity in maintaining numerical integrity.

The Multiplicative Inverse

In modulo arithmetic, the concept of multiplicative inverses enables division-like operations within finite fields, enhancing computational versatility.

Example: Multiplicative Inverse (Mod 13)

Consider the expression 5 * 8 (mod 13), seeking the multiplicative inverse of 5:

Multiplicative Inverse Example link_to_image_7

By finding the number that, when multiplied by 5, yields 1 (mod 13), we identify the multiplicative inverse of 5 as 8. This demonstrates the pivotal role of multiplicative inverses in modulo arithmetic.

The Case of 3 in Mod 12

Expression	Result
3 x 1	3
3 x 2	6
3 x 3	9
3 x 4	0
3 x 5	3
3 x 6	6
3 x 7	9
3 x 8	0
3 x 9	3
3 x 10	6
3 x 11	9
3 x 12	0

Problems with Multiples of 3 (Mod 12):

Limited Reach: Not every number can be reached from a multiple of 3 within mod 12 arithmetic.
Cyclic Results: The results exhibit cyclical patterns, leading to duplicity paradoxes.
Ridiculous Results: The presence of 0 as a result in the sequence raises questions about the logical consistency of the arithmetic.

The Good Case of 5 in Mod 12

Expression	Result
5 x 1	5
5 x 2	10
5 x 3	3
5 x 4	8
5 x 5	1
5 x 6	11
5 x 7	4
5 x 8	9
5 x 9	2
5 x 10	7
5 x 11	0
5 x 12	0

Advantages of Multiples of 5 (Mod 12):

Complete Reach: Every number can be reached from a multiple of 5 within mod 12 arithmetic.
No Cyclic Results: The results exhibit no cyclic patterns, ensuring logical consistency and avoiding duplicity paradoxes.
Logical Results: The results maintain logical coherence, with no unexpected or absurd outcomes.

Utilizing Prime Numbers in Mod Arithmetic

In the examples above, using 5 (a prime number) as the modulus in modulo arithmetic yields favorable outcomes, leading to a well-defined and structured sequence of results. This concept extends to prime fields, where the modulus is a prime number.

When a prime number is utilized as the modulus (e.g., mod 5), the resulting arithmetic operations exhibit enhanced properties, including complete reachability, absence of cyclic patterns, and logical consistency. Hence, employing prime numbers as moduli in arithmetic operations leads to more robust and reliable outcomes, paving the way for the establishment of prime fields in computational frameworks.

Power Operations

Exponentiation unfolds seamlessly within modulo arithmetic, leveraging consecutive multiplication to navigate numerical landscapes with precision and efficiency.

Example: Exponentiation (Mod 11)

Let's explore the expression 3^4 (mod 11):

Exponentiation Example

By consecutively multiplying 3 four times and finding the remainder when divided by 11, we arrive at the result, 4 (3^4 ≡ 4 mod 11), exemplifying the well-defined nature of exponentiation within finite fields.

Defining Generators (Mod p)

Generators play a pivotal role in modulo arithmetic, offering a structured framework for numerical exploration and algorithmic development. A member element whose power can reach every element in a finite field is called a generator (or primitive element).

A key property of generators is that raising them to the power of (p-1) yields 1: g^(p-1) = 1, where 'g' is the generator and 'p' is the prime modulus.

Consider the integer set {1, 2, 3, ..., p-1} within modulo p arithmetic. A generator, such as 3, possesses the unique property of generating all elements of the set through exponentiation:

Power	Result (3^power mod p)
0	1
1	3
2	9
3	10
4	13
5	5
6	15
7	11
8	16
9	14
10	8
11	7
12	4
13	12
14	6
15	2
p-1	1

By raising the generator 3 to various powers, we traverse through the entire integer set within the modulo p system, showcasing the versatility and power of generators in modulo arithmetic.

Through these examples and properties, we unravel the intricacies of generators in modulo arithmetic, illustrating their significance in computational frameworks and cryptographic protocols.

Modulo Identities

Law	Expression	Equivalent
Additive Distribution	(a + b + c) mod m	(a mod m) + (b mod m) + (c mod m)
Multiplicative Distribution	(a ⋅ b) mod m	[(a mod m) ⋅ (b mod m)] mod m

Prime Field vs. Non-Prime Field: Arithmetic Operation Comparison

Property	Prime Field	Non-Prime Field
Modulus	Prime number (e.g., 17, 23, 29)	Non-prime number (e.g., 12, 15, 20)
Additive Operation	Modular addition	Traditional addition
Subtractive Operation	Modular subtraction	Traditional subtraction
Multiplicative Operation	Modular multiplication	Traditional multiplication
Division-like Operation	Modular division (using multiplicative inverses)	Division (may not be well-defined)
Exponential Operation	Consecutive multiplication with modulo arithmetic	Conventional repeated multiplication
Resulting Properties
- Completeness	All elements of the field are generated	Some elements may not be reachable
- Predictability	Well-defined, consistent outcomes	Results may vary, leading to ambiguity
- Efficiency	Structured operations, efficient computation	Repetitive operations, potentially less efficient
- Stability	Logical, coherent results	Potential for inconsistency and unpredictability

In a prime field, arithmetic operations leverage the modulus of a prime number, ensuring completeness, predictability, efficiency, and stability. Modular arithmetic facilitates well-defined outcomes for addition, subtraction, multiplication, and division-like operations, with the aid of a generator for exponentiation.

Conversely, in a non-prime field, arithmetic operations may lack the structured properties of a prime field. The absence of a prime modulus and generator can lead to incomplete reachability, varied results, and potentially less efficient and stable computation. Traditional arithmetic operations may not be well-defined or may exhibit ambiguity and unpredictability.

Next Part would be focused on Set Theory & Group Theory . We are doing this to set the tone for Elliptic Curve Cryptography

Zero Knowledge Proofs Series #2

Prince Justice Sena Essiel — Fri, 08 Mar 2024 19:54:48 +0000

Zero Knowledge Proofs Objective: "Prove to someone that you have a piece of data / information that satisfies a claim without showing them the information you want to keep private"

Zero Knowledge in Action: A Movie Scene Analogy

Have you seen Quentin Tarantino's masterpiece, "Inglourious Basterds"? The iconic scene where Shosanna Dreyfus (Mélanie Laurent) tries to bluff her way past the cunning Colonel Hans Landa (Christoph Waltz) is a great example of a zero-knowledge proof in action! Please watch this short video before continuing

https://www.youtube.com/watch?v=2RhaBv3vEao

Shosanna (Prover): Tries to convince Landa (verifier) she's a has written a famouse person without revealing the information on her card.
Challenge (Questions): Landa throws questions related to her knowledge of the cinema (unique characteristics of the truth).
Proof (Answers): Shosanna's answers, without revealing her cards information (keeping information private).

The Building Blocks of Zero-Knowledge Proofs

Just like the game Shosanna plays with Landa, zero-knowledge proofs follow a specific structure:

Setup and Rules:
Establish a clear protocol for interaction between the prover and verifier.
Challenges:
The verifier throws challenges to test the prover's knowledge (not directly revealing the truth).
Challenge-Based Questions:
These questions are linked to the specific information the prover wants to keep hidden.
Verification:
The prover's responses convince the verifier with a high degree of certainty (not absolute, but very good!).
Probabilistic Confidence:
There's always a tiny chance a cheater might pass the test, but well-designed protocols minimize this risk.

Real-World Example: Age Verification at the Club

You (the prover) want to prove you're at least 25 without revealing your exact age. Here's how a zero-knowledge proof can be applied:

Age Claim: The bouncer asks you to claim your age (you claim to be 25 or older).

Verification: The bouncer performs calculations based on your claimed age (25) and the chosen modulus (m = 100):

Calculate both possibilities based on the hidden coin flip:
Heads (H): verification_H = (25 - 1) mod 100 = 24

Tails (T): verification_T = (25 + 2) mod 100 = 27

Proof Revelation: The bouncer asks you to reveal the proof value you calculated earlier.

Verification Check: The bouncer compares your revealed proof with the two calculated verification values:

If your revealed proof matches either verification_H (24) or verification_T (27), the proof is considered valid.
This indicates you know a value (x, your age) that satisfies the age requirement (greater than or equal to 25) without revealing the exact value.

Example:

Let's say you actually are 28 years old (x = 28).

You secretly flip the coin, and it lands on tails (T).

Following the prover steps, you calculate your proof: proof = (28 + 2) mod 100 = 30.

You claim to be 25 years old to the bouncer.

The bouncer calculates verification_H = 24 and verification_T = 27.

You reveal your proof (30).

The bouncer sees that 30 matches verification_T (27), confirming the proof is valid.

This protocol demonstrates zero-knowledge proof:

Why Zero-Knowledge Proofs Matter

Zero-knowledge proofs have numerous applications, from secure online transactions to protecting user privacy. They offer a powerful way to verify information without compromising sensitive data.

Next Steps: Diving Deeper

In our next blog post, we'll explore the mathematical concepts behind zero-knowledge proofs, including finite fields, modular arithmetic, and group theory. But fear not, we'll keep it approachable and focus on the core ideas!

Stay tuned for part two, where we'll unravel the mathematical magic behind zero-knowledge proofs