Introducing the MB09 algorithm and an attempt at demonstrating Fermat’s Last Theorem

First, we will start with some considerations regarding the algorithm and reintroduce Fermat’s Last Theorem. The first time I presented MB09, it was as an encryption algorithm, but effectively it is much more of a protocol for digital payments. As I have already mentioned, while blockchain and cryptocurrency were not yet well known, I developed MB09 as an encryption/decryption algorithm to exchange a message between two actors. Many years later, I worked on the algorithm, taking it as the basis for a fully homomorphic encryption system and creating MB23, which was a fully homomorphic algorithm. Eventually, in 2020, it was turned into a new version, called MBXX, to overcome the consensus problem proposed by Satoshi Nakamoto and its related technology: the Bitcoin blockchain.

Let’s examine how the first version of the MB09 algorithm worked:

1. To do that, we’ll recall Fermat’s Last Theorem:

Here, the n exponents represent all the sets of positive integers.

This equation, as we already know, has been demonstrated to be never satisfied except for the n = 2 exponent (which is the well-known Pythagorean theorem), as follows:

2. Diving deeper to analyze this simple yet complex equation, we find that in modular mode, by substituting the n exponents with a set of prime numbers, p, in the first equation, the following equation’s results are always verified for the modular math addition property:

In simple words, the second equation shows that the sum of a^p+b^p is always verified to be z^p for all primes >2. The proof of its verification is the following:

• Fermat’s Little Theorem states that a^p ≡ a (mod p), b^p ≡ b (mod p), and so on to z, where p is a prime number. Remember p is a prime number and it’s the same parameter both in the elevation and in the module.
• From the sum elementary math property, we have:

• If we substitute a with a^p (mod p), b with b^p (mod p), and z with z^p (mod p), it stands that a^p+b^p ≡ z^p (mod p) is always verified.

3. Continuing with the result from the start of step 2, we can also conclude that, for all of the (p) exponents (at the opposite of its correspondent linear equation mode), the sum of (a+b)^p is always verified, and it’s equal to z^p. In other terms:

For example, consider the following modular sum:

So, we can re-write the preceding equation in step 2 in the following form:

Alternatively, for the modular sum property, we can even write it in the following simplified form:

That means if we put a prime number (p) as an exponent and even the modulus with the same (p) value, then the preceding equation (in modular mode) returns to linear mode, so that (a+b) is always equal to its sum, (z).

At this point, I could hazard a demonstration:

1. In step 3, we reached the point of rewriting the equation to .
2. In step 2, we demonstrated (following Fermat’s Little Theorem) that the equation results are always verified for all p>2.

For example, if we try p =11, we have:

3. The sum of is always , as we have previously seen. So, this equation (in modular mode) is always verified to be valid in the opposite way of what we want to demonstrate in linear mode: the sum must always be denied zⁿ.
4. But still, we have a problem: the exponent n is an integer number and not just a prime number p. Is this a real problem? If I demonstrate that it is valid for any p, is it valid for all the integer numbers?
5. Now let’s assume by contradiction that the following equation (putting p’ instead of p as the module) would always be verified:

Where (p’) is the set of all the prime numbers > . So, by definition, we can also take p’>z.

Can you catch the meaning?

If , we are dealing with a sum of expressed in linear mode, no longer in modular mode, because the operation performed with the sum falls back inside the ring (Zp’).

For example, let’s assume that the first prime number after is p’:

So, we calculate the equation in (mod 8589934609):

There is no difference in performing such an equation in modulo p’ or in linear mode.

1. In fact, both equations will never be satisfied.

That’s because for Fermat’s Little Theorem, again, we have:

Consequently:

As a result, in step 5 of this demonstration, we had wrongly assumed .

So, now we must assume that:

This last equation is equivalent to writing:

That was what we wanted to demonstrate for the Fermat version with prime exponents.

Now, returning back to MB09, the following equation is what Fermat’s Little Theorem explains, and it determines the preceding linear function:

For example, consider the following:

You might not have noticed, but in the preceding function, we used the equal symbol (=), not the symbol ≡, which means congruent notation. In this case, the meaning of = is very important because we mean equal in its absolute values, so 3 is actually 3, and not just congruent.

I understand that all this could appear a little bit fuzzy, but try to follow me a little bit further ahead and the fog should disappear.

Fermat’s Little Theorem states that a^p = a (mod p) if a<p. So, what happens if we assume a>p?

For example, let’s try with a = 5 and p = 3:

As you can see, (a) is no longer equal to (a) in its absolute value if a>; the result is only congruent.

This intriguing property caused me to bear many considerations in mind regarding Fermat’s Little Theorem, the most important of which here is the formulation of the following hypothesis:

“If I take a>>p (much greater than p) and I keep [a] secret, then this will be a one-way function where it will be very difficult to return from the result, let’s say from (A) to [a].”

Let’s look at an example.

You can verify that 5³ ≡ 2 (mod 3), but also 8³ ≡ 2 (mod 3), and 11³ ….14³, 17³ are all congruent, and so on infinitely.

As you might have gathered, the curious thing is that starting from an initial value of 5 and adding 3 + 3 + 3… (essentially, adding 3 sequentially), we always obtain the same value (2) in (mod 3), which is different in absolute value from (5), as Fermat’s Little Theorem states when p > a.

Finally, at the time, I wanted to demonstrate that it is very difficult to come back from a public number (A) to a secret number [a] if p < a.

Let me explain this concept with an example taking a larger [a]:

That is, it would be easy to reduce this number to its corresponding modulo p=3.

In fact, we have the following:

Conversely, if I know the public number, (A) = 2, where the following is true:

Then, even if an attacker knows p = 3, it will be very difficult to attempt to obtain the [a] private key if a>>p:

The simple reason for this is that p = 3 is our (Z^p) ring, but [a], the private secret key, is outside of the (Z³) ring, and you don’t know when to stop the iteration to find number [a]. Theoretically, [a] could be all the numbers from (p) to infinity and it doesn’t matter how large [a] is because, computationally, it is very easy to obtain (A) from [a] but not vice versa. However, all that works but only in some instances.

Now that you know the basis on which MB09 leans, you will probably be curious to learn how it was implemented in its first version.

Important note

I have represented, with a lowercase [a] letter, the hidden elements of the equation and, with the uppercase (A) letter, the known elements. However, don’t be confused by this, and don’t assume that A > a just because the letters are lower and uppercase. In fact, it’s the opposite: in mathematical terms, A is much smaller than [a].

An extensive explanation of the MB09 algorithm

As I mentioned earlier, the MB09 system is based on public/private key encryption principles. However, the scope here is not to send and receive a message between two (or more) actors. MB09 doesn’t work correctly if used for this scope. However, the scheme of the algorithm works well for the scope to set up a protocol to manage and transmit digital cash in anonymity and secure the transactions.

Eventually, one of the purposes of implementing such a system is that the network works as an autonomous system. I will explain this concept better in the next section when introducing MBXX, which is the evolution of MB09 in a decentralized environment. The version I’ll present now, starting from a centralized system, will migrate to a decentralized and distributed system, as we will discover in MBXX.

In the next section, I will explain the basic concepts of a network governed by crypto algorithms, where Z (the centralized administrator) must verify whether all the transactions made by the users are correct and acceptable.

Z is our network’s centralized administrator; you can think of it as a telecommunication provider or a bank. Alice and Bob are two actors in the network.

Bob is the sender, and Alice is the receiver. They can be considered virtual machines, servers, or computers. In our basic example, they are part of a network in which there are many users. The network’s admin (Z) is a server that is linked to many users, as you can see in the following diagram of a centralized network:

Figure 6.3: A centralized network

Z has already published some parameters such as the prime number (p) and the public keys, (A) and (B), of Alice, Bob, and other participants.

We will proceed to look at the algorithm with only these two actors. Still, as I have already mentioned, this algorithm’s strength is just the possibility of operating with many users who don’t know each other, who don’t trust each other, and who don’t trust third parties.

Indeed, Fermat’s Last Theorem (which is extended in modular form), in this case, applied to MB09, is valid also for an infinite number of users of the network, as you can mathematically see here:

Important note

I have illustrated the operations with a sum (+); however, all of these operations could be performed by XOR, difference, or multiplication.

The [M] message has previously been encoded with ASCII code (as we learned in the first chapter), and you can think of [M] as an amount of digital money to transfer between (A) and (B).

Now, let’s demonstrate whether Alice and Bob can transfer money to each other using the algorithm mathematically.

Each step of this algorithm after the key initialization consists of a recursive iteration of the following:

• Implementation of the public parameters of the users
• Operations on the parameters: the transmission of the messages (for example, a digital money transfer)
• Re-valuation of the new parameters

Key initialization:

• [a]: This is the private secret key of Alice.
• [b]: This is the private secret key of Bob.

This assumes that [a] and [b] are two random large primes.

Public parameters:

Alice and Bob calculate their public keys starting with their private keys:

• 
• 
• 
• 

At this point, you can visualize the two f(z) and f(Z) equations. The first is in modular mode, and the second is transformed into linear mode:

The correspondence between the first equation’s elements and the second equation’s elements is essential for the algorithm. As you can observe in the following diagram, each element of the first equation can be represented with an element of the second equation.

The peculiarity of this correspondence is that, while in the first equation, the operations have been performed using the users’ private keys; in the second equation, the operations are performed with the public keys of the users. You can see that the arrows are only going in one direction, from [a] to (A), and it’s difficult, as we have seen, to go back from (A) to [a] if [a>>p]:

Figure 6.4: The correspondence between the elements of two equations

Here, (Z) can be defined as the isomorphic balance between the operations performed with the parameters expressed clearly, instead of inside the square brackets, representing the secret parameters of the f[z] function.

At this point, MB09 (version 2009) went on with a standard cryptographic transmission based on a pair of keys to transmit a message between Alice and Bob.

Important note

Remember that, here, [a] and [b] are Alice and Bob’s secret values. Moreover, don’t confuse the letters [a] and (A), thinking that (A) is bigger than [a] just because the first is represented in capital letters.

First, we have to generate the secret transmission key, [K]. This is a shared transmission key that can transmit [M] between Alice and Bob. It can be generated with any public/private key algorithm, just like the D-H algorithm.

Indeed, in the first version of MB09, I adopted the [K] key generated by D-H. However, as you might have gathered, it’s possible to generate [K] with any other algorithm that uses the [a] and [b] secret keys of Alice and Bob as input and gives a cryptogram, (c), as output.

Important note

(c) is the cryptogram represented inside round brackets. Here, I use (c) because we have only two actors. In other cases, I will use another notation; don’t confuse it with an element of the network.

The representation of the algorithm with only two actors (but as I said, this is a multiple-communication algorithm) is as follows:

Alice encrypts [M] using her [K_a] secret key, where [K_a] has been generated by any public/private key algorithm, and obtains the cryptogram (c):

Important note

Here, as I have already mentioned, (c) is the cryptogram, which is obtained through the multiplication of the secret message [M] with Alice’s private key [K_a]. In the original version of the algorithm, I used multiplication as the operation to generate (c). However, it is possible to implement it with a different encryption method, such as Bitwise-XOR or scalar multiplication.

Bob decrypts [M], generating a [K_b] secret key such as the following:

For instance, if we assume the use of this algorithm in a digital cash environment, such as the transmission of digital cash in a payment system, [M] will be the real amount of digital cash transacted, while (Hm), its corresponding hash value, will represent the hash of [M]:

The operations performed on the first equation (at the top), encrypted, give the result [z] linked by an operation to the message [M] “in blind” that corresponds with the operations performed by the second equation’s elements and matches the result of the linear equation (Z). We will experiment with a similar protocol later in this chapter when we discuss the MBXX protocol.

Essentially, (Z) represents the homomorphic balance of the system, as the digital money transacted doesn’t change the value of (Z). The scope to adopt such a homomorphic balance is that the administrator has, in each instance, a corresponding balance of the total amount of cash with the isomorphic values and can control the accuracy of the transactions even when the transacted amount, [M], is unknown. If you’re struggling to understand (Z), note that we will be working with (Z) again when we look at the MBXX protocol, particularly in the Notes on the MBXX protocol section.

Let’s perform an exercise using a D-H key exchange:

• [a] and [b] are the secret parameters of Alice and Bob.

As we know, the public parameters in D-H are as follows:

• p: Large prime number
• g: The generator of the (Z^p) ring

The exchanging of [M] is performed as follows.

Step 1: Encryption

Alice generates her public key (Ag) starting with her secret parameter, [a]:

Bob generates his public key (Bg) starting with his secret parameter, [b]:

Alice calculates the following:

Alice encrypts [M] with her [K_a] key:

Step 2: Decryption

Alice sends (c, Ag) to Bob.

Alice sends the hash value of [M] = (Hm) to the administrator.

Bob decrypts (c), returning [M]:

Note that is just the inverse modular operation of multiplication. You can figure it out like a division: . You can refer to Figure 6.5 for a complete scheme of the algorithm applied to the transmission of a secret message.

If we consider the private keys of Alice and Bob, [a] and [b], as values of their accounts and [M] as the amount of digital cash transmitted, we have a third step, which can be regarded as the homomorphic balance.

Step 3: The homomorphic balance

Transposing the value of [M] both into the first equation and the second equation, the admin can verify that the transaction between (A) and (B) is correct:

Pay attention to the following in the function of the encryption:

As I have said, I have used the multiplication between [M] and [K] to encrypt [M]. However, we can also implement the encryption with another operator, such as Bitwise XOR, between the message [M] and the key [K]. Note that, here, the algorithm of the transmission adopted to send [M] is not as important as the logical structure of the protocol for the implementation of multiple transmissions.

Indeed, the logical structure of this algorithm is not crafted for two users but multiple users.

In this scheme, it is supposed that the admin knows the amount of money originally held by the users. Let’s look at an example:

Figure 6.5: The original version of the patented MB09 published in the Patent Cooperation Treaty (PCT)

At the time, together with my colleagues, we crafted a Proof of Concept (POC) to demonstrate that MB09 could work well to exchange digital cash. We implemented a transmission of digital crypto cash between cellphones. The protocol used was based on a modified version of MB09, which I have presented here. It was added to the operative elements to engineer implementation.

In May 2010, the payment system based on MB09 was selected as a candidate for digital payments by a telecommunication company. This company then acquired part of the rights on the patent of MB09 and entrusted our research laboratory with a research project to implement another private/public key algorithm, MBXI, which we will examine next.