ASecuritySite Podcast

Please note, I slippled up a little in the podcast, and where the army size if 187,000. I have updated below.

Web page: https://billatnapier.medium.com/cryptography-fundamentals-6-chinese-remainder-theory-ctr-2d1874943f15

And so a large army met. The general asks the collected troops to arrange themselves into groups of 50. He counts that there are four troops left without a group. He then asks for groups of 60, and there are 14 left, and finally, he asks for groups of 70, and there are 24 left. The general stands up and tells the army that they are 201,554 strong. So how did the general do it?

>>> army%50

4

>>> army%60

14

>>> army%70

24

>>> print (army)

187000

Solution: https://asecuritysite.com/principles_pub/crt02?val1=4,14,24&val2=50,60,70

The Chinese remainder theorem was first published by Chinese mathematician Sun Tzu. It determines a number x so that, when divided by some given divisors, leaves given remainders. As public key encryption typically involves this type of operation, CRT is well set up to help to crack encrypted messages. So what value will x equal in the following [Soln]:

x mod 3 = 2x mod 5 = 3x mod 7 = 2

The answer is 23, as 23 divided by 3 gives 21 remainder 2, 23 divided by 5 gives 4 remainder 3, and 23 divided by 7 gives 3 remainder 2.

CRT and RSA

If we capture enough RSA encrypted messages with the same e value and different modulus values (N), we can crack the message using the Chinese Remainder Theorem (CRT). For example, if we have an e value of 3 we just need to capture three cipher messages to be able to recover the message.

In this case, we will use the following (where p1 and q1 generate N1, p2 and q2 generate N2 and p3 and q3 generate N3):

e=3, message=123456789123456, p1=1131701, q1=1131721, p2=1131727, q2=1131737, p3=1131749, q3=1131751

The run then gives:

eGCD of N values: 1N1= 1280769787421 N2= 1280817319799 N3= 1280858062499Message= 1234567891234 e= 3Cipher1= 184224238921 Cipher2= 173356604414 Cipher3= 369941826218

The equations we have to solve are then:

M^e mod 1280769787421=184224238921M^e mod 1280817319799=173356604414M^e mod 1280858062499=369941826218

If we now use Chinese Remainder Theorem we get a result of:

Result (M^e) is: 188,1676,377,431,587,319,857,436,861,793,600,904

And then we just use: 10^(log10(M^e)/e)

and recover the message of 1234567891234

Try here.

A more detailed example is [here]:

N1= 20439437 N2= 20684303 N3= 20830087Message= 1500000 e= 3Cipher1= 6509102 Cipher2= 9683741 Cipher3= 3214286 =======Equations to solve=======M^e mod 20439437=6509102M^e mod 20684303=9683741M^e mod 20830087=3214286 ======Chinese Remainder Theorm Calc========Result (M^e) is: 3375000000000000000 Calculated value of m is 1500000 Using 10^(log10(M^e)/e)

We can also use:

M=res**(1.0/3.0)M=libnum.nroot(res,3) CRT is good, sometimes?

Well, in RSA, we can use Chinese Remainder Theory to simplify the decryption process. We will cover this in more detail when we look at RSA encryption. For now, all we can say that for RSA keys we also generate values of dQ, dP and InvQ to use CRT to speed up decryption.

Other attacks

CRT is a widely used cracking technique in cryptoanalysis. Werner Schindler [here] defined a timing attack on RSA which involves a factorization on the RSA modulus if CRT has been used. The work goes back to 1996 when Arjen Lenstra defined an attack against an optimization (called the CRT). If a fault was generated in calculating a signature (using RSA-CRT optimization), the attacker could recover the associated private key from a signature. This is known as the "RSA-CRT key leak".

Many systems have been immune from this attack as TLS did not use an RSA signature. Unfortunately, the forward security option in TLS is now being recommended, and this has re-introduced the problem.

Researchers at Red Hat [here] also now found many Web sites which were not hardened against this type of attack and found quite a few with RSA-CRT key leaks (none of which were code repositories). They found that the private key of a Web site can be leaked to the intruder, who can then decode all of the encrypted communications with the site and also impersonate it.

Forward secrecy is used with a key-exchange method and uses a session key which derives itself from a given set of long-term keys and which will not reveal the session key even in the long-term keys are breached.

How do we protect against this?

There are two ways to defend against this attack. The first is to make sure that e always exceeds the copies of messages that can be copied, and the other is to pad messages with random bits. In most applications, now e is 65,537.

Cryptography Fundamentals 5: GCD, Extended GCD and Group Generators

This podcast will outline a few building blocks of cryptography: GCD (Greatest common divisor), extended GCD and group generators. These you will find in many related cryptography papers, and any weaknesses in these can cause significant problems to the overall security of a method.

Greatest common divisor— GCD

A fairly simple concept that is used within public key encryption is the greatest common divisor (GCD). With this, we take two integer values and determine the largest factor that they are. Overall, every non-prime number is made up of the multiplication of prime numbers. For example:

32,128 = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 251

36,281 = 7 x 71 x 73

So, the GCD of 56 and 42 is 14, as both of the values can be factorized into 4 x 14 and 3x14, respectively. https://asecuritysite.com/principles_pub/gcd

Normally we use this function to find values which do not share a factor, as we will see when selecting the public exponent (e) in the RSA method. The method to determine the GCD is fairly simple, and where we take two values (a and b) and use the modulus operation to find the GCD:

def gcd(a, b): while( b != 0 ): Remainder = a % b; a = b; b = Remainder; return a;g = gcd(679,99)print g

A sample run shows that 679 and 99 do not share any factors:

a:679, b:99, Remainder:85a:99, b:85, Remainder:14a:85, b:14, Remainder:1a:14, b:1, Remainder:0Return value:1

Web: https://asecuritysite.com/encryption/gcd

Extended GCD

GCD is the greatest common divisor. For two integers (x and y), the extended GCD method solves ax+by=v for a and b, and where v=gcd(x,y). One example of using the Extended GCD method is to determine the modulo inverse of a value (the inverse value of n (mod p) so that:

n⋅n^{−1}=1 (mod p) ).

30a+20b=gcd(30,20). Soln: a=1, b=−1. Try!

35a+15b=gcd(35,15) . Soln: a=1, b=−2. Try!

Group generator

In reading about cryptography, have you ever come across the term of a cyclic group G of order p and with a generator g? With a discrete log mapping, we map x to Y with

Y=g^x (mod p)

where we have a generator value (g) and a prime number p. The challenge is that even though we know Y, g and p, it is extremely difficult to determine the x value if we use a large prime number.

But can we use any value of g, and should it be as large as possible? The answer to both of these questions is no. If we select a prime number of 11, and then select g values of 2, 3, 4 …10, and then calculate the results we get [spreadsheet]:

Now look at g=2 and p=11, for 2¹ (mod 11) we get 2, 2² (mod 11) we get 4, 2³ (mod 11) we get 8, and so on. As we see {1,2,3,4,5,6,7,8,9,10} gives {2,4,8,5,10,9,7,3,6,1}, and where all the input values give a 1-to-1 mapping to another value in the group. But if we try g=3 and p=11, we get x=1 gives 3, and for x=6 also gives 3. The mapping is now {1,2,3,4,5,6,7,8,9,10} to {3,9,5,4,1,3,9,5,4,1}, and so we are not using the full range, and where there would be a confusing for mapping back to our original value.

But, in order to demonstrate the principle, I have done this in a long-handed way, so how do I find out all the possible values of G for a given prime number (p)? Well, here's a nice simple method in Python that I created to test up to p):

import sysdef issafe(g,p): exp=1 rand=g next = rand % p while (next != 1 ): next = (next*rand) % p exp = exp+1 if (exp==p-1): return True else: return Falsep=11g=4if (len(sys.argv)>1): p=int(sys.argv[1])if (len(sys.argv)>2): g=int(sys.argv[2])print ("Is g={0} safe for p={1}? {2}".format(g,p,issafe(g,p)))print ("x\tg^x\tg^x (mod p)")for x in range(0,10): print ("{0}\t{1}\t{2}".format(x,pow(g,x),pow(g,x,p)))

A sample run with an unsafe value is:

Is g=3 safe for p=13? Falsex g^x g^x (mod p)0 1 11 3 32 9 93 27 14 81 35 243 96 729 17 2187 38 6561 99 19683 1

and where the only output value is 1, 3 and 9. For a safe value, we get:

Is g=3 safe for p=17? Truex g^x g^x (mod p)0 1 11 3 32 9 93 27 104 81 135 243 56 729 157 2187 118 6561 169 19683 14

So, how does this work in practice? Well, rather than picking the prime number and then finding a g value which will work, we typically pick the g value we want, such as for g=2, g=3 or g=5, and then find a prime number of a given size to work with that value. This will slow down the process, as we might have to pick a few prime numbers before we find one that will work. An example command in OpenSSL to generate the Diffie-Hellman parameters for g=3 and a 512-bit prime number is:

openssl dhparam -text -3 512DH Parameters: (512 bit) P: 00:ff:1a:a6:fd:94:1b:55:8c:03:e0:ba:91:d5:e3: 23:40:6a:8e:49:a1:d4:d9:dd:68:3f:10:3d:ff:a7: a6:8e:2f:9f:f9:3f:4d:dc:3d:54:71:e0:aa:65:dc: 24:03:42:73:39:db:d6:02:a6:dc:bd:ac:49:12:a8: dc:d0:57:d9:bf G: 3 (0x3)

https://asecuritysite.com/openssl/dh

We live in a legacy world of money. Our transactions are often still based on moving paper money around, and we have basically scaled this into a digital world. At the core of this is the lack of any real cryptographic trust in digitally signing transactions.

For this, the Bank of England is now discussing a CBDC (Central Bank Digital Currency) [2]:

And before you reach for Ethereum smart contracts and ERC tokens, there's a catch. This is not actually a cryptocurrency, but an electronic payment system. Basically, it will basically be a digital currency, and thus link these coins to a digital wallet which is held by a trusted payment entity (such as a bank or payment provider).

The overall proposed architecture is to use a central bank ledger, which validates transactions. This would not contain any personal data on users and integrate at an API level. Access to this API for users would be through intermediaries — trusted and regulated payment providers. Users would not be able to interact with the core ledger without using an intermediary.

Figure 1: Platform model [2] CBDC model

To transfer funds in a traditional way, Alice contacts her bank and enables a transfer to Bob's bank. The transaction basically involves account numbers and sort codes and is transferred through a trusted payment gateway. This is identified with the purple line in Figure 2.

In the CBDC model, Bob and Alice will own a digital wallet in their bank, and where Alice can move digital tokens from her wallet to Bob's. Overall, Bob and Alice can move money between their bank account and their digital wallet. The moving of their funds into the digital wallet gives lesser control of funds than the maintenance of bank accounts.

Figure 2: Traditional payment v cryptographic payment

In a traditional cryptocurrency system, Bob and Alice have a public blockchain wallet that contains their private key. In Ethereum, we transfer ERC20 tokens using a digital wallet. This digital wallet contains the private key to sign off the transaction. A smart contract then maintains a table of the owners of each of the ERC20 tokens issued. This relates to the wallet identifier as a hexadecimal address. This is identified as the red line in Figure 3.

Figure 3: Cryptocurrency transaction using ERC20 tokens (red line) The state-of-the-art

There are several existing models for a CBDC, including Project Hamilton, and which is a collaboration between the Federal Reserve Bank of Boston (Boston Fed) and MIT [1]:

The targets are for a minimum of 100,000 transactions per second and for 99% of all transactions to be completed within five seconds. There should be no loss of funds in the event of a data outage, and privacy is a fundamental part of the design.

An important element of the design is the use of intermediaries and custody. In terms of trust, we have intermediaries — such as banks, and payment service providers — and which are custodians of the digital wallet. But there is the opportunity for customers to own their own digital wallets — as with an Ethereum wallet. The model can then be "direct" — customer-to-central bank, or "two-tier" — central bank to intermediatory (Figure 4).

Figure 4: Two-tier model — central bank to intermediatory

The proposed method decouples fund checks with transaction validations. Funds are stored as a 32-byte hash value with an Unspent funds Hash Set (UHS) — Figure 5. The transaction has a similar format to Bitcoin.

Figure 5: Unspent funds Hash Set (UHS) Economic concerns

The speed of the transactions and the ease of access to digital currency could enable economic risks

Reduced lending opportunities

As the digital coins are moved to a wallet, they will thus be out of the control of a bank, which means that they could not lend the money to another person — which kinda defeats one of the main functions of a bank. If too much of this money was moved to wallets, it could cause the lending system to stall.

Bank runs

There have been many occurrences of runs on banks, including with Northern Rock. With this, customers queued to get access to the funds, and which generally slowed down the pressures on withdrawals. With a digital pound, this could be made much worse, as customers could withdraw their funds with a simple transfer. Banks could thus risk a run on their funds.

Cybersecurity?

Generally, we trust our banks to look after our money. With a digital wallet, attackers could target hacks, which could have lower levels of control on access to the wallet.

A core part of the Bank of England's strategy for the digital pound is to develop resilience in both the technical and financial disuptions involved [2]:

Technical challenges

The enablement of a CBDC brings many technical challenges.

Privacy and auditability

There is a significant balance between privacy and auditabilty. The use of zero-knowledge proofs will allow for privacy within transactions, but this will hide the sender and recipient of a transaction. This privacy, though, can restrict auditability and reduce the opportunities for law-enforcement investigations.

Programmability

Most current models must have the full state transition of a transaction to be in-place for a transaction to go ahead (to avoid double spending). Within contract implementations, there may be intermediate states that allow for the digital pound to exist in an intermediate state awaiting an event. For example, Bob might commit to paying Alice for a new car, but she will not accept shipping the car until Bob commits the funds. Once she ships the car, the funds would then stay pending until Bob confirms its receipt. This smart contract associated with the transaction would thus need to store the state of the intermediary state, and not release the funds to Alice until there is a digital proof of receipt from Bob (Figure 6).

Figure 6: Programmability Interoperability

A major focus for the digital pound must be the interlinkage with existing Layer-2 payment channel networks. This would also support cross-border transactions but will require integration with other CBDCs in other countries.

Offline payments

In the likely model for the digital pound, there is an interaction between the central bank, and the transacting parties (Bob and Alice). In some circumstances, there could be no Internet connection, and thus there needs to be an offline transaction. This type of transaction will likely require a secret enclave to be setup on a hardware payment device so that the transaction could not be tampered with.

Minting and redemption

It is likely that the CBDC will be responsible for minting and removing the digital tokens. Each of these would be digitally signed by the issuing bank. But, the great risk here is the use of the private key to sign the transactions of the central bank. If an insider in the Bank of England gained access to this, then tokens could be issued or even removed by malicious entities — this is equivalent to printing forged bank notes.

Productionization

While models exist as prototypes, the scale-up to a national level would involve extensive design and implementation skills to make sure there were no ways to compromise the infrastructure.

Denial of service attacks

In a model where Bob and Alice own their private keys, there are no fees for a payment. This means there is no cost to support payment transactions, which means that it could be susceptible to a Denial of Service against the infrastructure — as it will not cost anything to flood the system with valid and invalid transactions. Likely mitigations here are rate-limiting, and the enforcement of a cool-off period before money can be respent on another transaction. Along with this, there could be proof-of-work transactions (such as computing a hash value of a given complexity for each transaction), or fees charged for a given volume of transactions.

Quantum resistance

Existing public key encryption methods — such as ECC and RSA — are at risk against quantum computers. The infrastructure that we create must be resilient to a medium-term attack against transactions. Currently, NIST has defined that Dilithium, FALCON and SPHINCS+ are the preferred solutions for digital signatures, and should replace RSA and ECDSA signatures. For key exchange, Kyber is recommended as a replacement for ECDH. It is likely that any digital currency will support these methods, alongside existing public key methods — but will migrate in time to the post-quantum robust methods.

Conclusions

It is an exciting time. A digital currency will open up new areas of innovation, but one slip-up could bring the whole of the financial infrastructure down in an instant. I repeat again, this is not cryptocurrency, but a trusted digital payment infrastructure. There are good opportunities to improve the detection of fraud and scamming, and truly move to a more trusted financial world.

References

[1] Lovejoy, J., Fields, C., Virza, M., Frederick, T., Urness, D., Karwaski, K., … & Narula, N. (2022). A high performance payment processing system designed for central bank digital currencies. Cryptology ePrint Archive.

[2] The digital pound: Technology Working Paper, Bank of England, 2023.

Scott Helme is a Security Researcher, Entrepreneur and International Speaker. He is the creator of the Report URI and Security Headers Web site. More details:

https://scotthelme.co.uk/

I will bet you, that you have a memory of school where you had the "pleasure" or, most likely, the "nightmare" of performing long addition or long subtraction, and where you had carry overs between columns. The units carried over in the tens, the tens into the hundreds, and so on. And, then, you encountered long multiplication with those ever growing list of numbers.

And, please forgive me, you progressed to long division, and you had that divisor dividing into your number and with the bar along the top, and where you put your result, and which those pesky remainders. "Oh, teacher, 61 divided by 9 is 6 remainder 7". And, didn't you love throwing away that remainder and just making the answer 6. But, in cryptography, the remainder is the bit we like, and we throw away the other bit. So for us, 61 mod 9 is 7.

So, just take a pause now to just calm yourself for those memories. If you want to leave now, please do so, as we will revisit some of these memories, but, hopefully, we will make things a whole lot more simple.

To these additions and multiplications in an electronic circuit or some software code can take many operations. But, just imagine a world where you did not need to carry over values from one column to another, and even where all you had to add or multiply was a 0 and 1, life would be so much easier, and these school nightmares would end for you, and life would be so much happier for your kids in learning maths.

For example, if we have a binary adder we have 0+0=0, 1+0=1 and 1+1=0. As we see a simple binary adder just throws away that pesky carry. If we add 1+0+1+1+1+0, we see an answer of 0. But in our normal maths, to add 7+4+3+9+8 requires us to add up the units, and carry over in the 10s column. For simplifying things we turn to Évariste Galois.

Évariste Galois — who lived from 1811 to 1832 — died of duelling wounds at the age of 20 but left a great legacy. While he was a teenager, he worked on polynomials and laid down the principles of Galois's theory — along with defining the concept of a finite field.

Creating the reverse operation

As we have seen from the previous podcasts, we have values in a group, and then can operate on these to get another value in the group. So, if we have a group of 0 to 16, we can constrain our values with a (mod p) operation, and where p is a prime number.

For example, if we use a prime number of 17, and we take a value of 2 and then raise that to the power of 5 and take the mod of 17, to get 15:

>>> pow(2,5,17)15

For all of the values from 0 to 16, we should (hopefully) get different mappings for the output. This will then allow us to reverse back by taking the inverse operation to the modulo power. This, as we have seen from a previous podcast, is to subtract one from the prime number (PHI=p-1), and perform an inverse of the base modulo of the prime number minus one. A simple Python program gives us the result for the inverse:

>>> pow(5,-1,16)13

If we now multiply our result of 15 by 13 and take (mod 17), we magically get our value back again:

>>> pow(15,13,17)2

In this way, we aim to reverse our mathematical operations, and where there is no confusion about the reverse operation.

Simplifying things

Up to now, we have seen that we have operated on our normal arithmetic operations for the (mod p) such as add, subtract, multiply and divide, but we can simply things even more if we have a field which has 2^n elements, and where if n is 8, we can have 256 elements. 256 elements, for example, is the number of values we can have for a byte of data in a computer system. If so, we can convert our bit values of our integers into a polynomial, and then operate on them as polynomial operations, such as:

(x²+1)+(x) = x²+x+1

This, as we will see, significantly reduces the complexity of our arithmetic operations, and rather than have complex circuits for adding (with carry overs) and multiplying (and where we end up with a value which has more bits than the inputs values), we constrain the calculation within our finite field. Along with this we then just need simple 1-bit adder or multiplication operation. So from complex adding and subtraction circuits in hardware or with software operations, we end up with simple bit operations. This vastly increases the speed of our cryptographic operation.

This is a Galious field, and defined more generally as GF(p^n), and where p is a prime number. But, in most cases, p will be 2.

Arithmetic operations

Within a finite field, we limit the number of possible values in a group. As we have seen this can be a prime number and where we get a group from 0 to p-1, and where we can perform our mathematic operations with the (mod p) operation. And, so, even though we have a finite field, we still want our maths to still operate as normal. The rules for every element in the group is:

• Commutative law. This is where (a+b) equals (b+a), and (a*b) equals (b*a).
• Associative law. This is where a.(b.c) is equal to b.(a.c).
• Distributive law. This is where a(b+c) is equal to ab+ac.
• Additive and Multiplicative Identifies (0 and 1). This means that a+0=a, and a times 1 is equal to a.
• Additive and Multiplicative Inverses. This means that there is an additive inverse where there is a value of b for a so that a+b=0. For multiplicative inverse, there is a value of b for a so that a.b=0.

Within our finite field in cryptography, we want all of these to work, so that we can reverse any operation that we can apply.

A Galois field

Within a field, we can operate on values in the field using arithmetic operations. We can thus have an infinite field and where we could include all of the possible integers. A Galois field of GF(p^n) has p^n elements. Typically we use GF(2^n). And so GF(²⁴) has 16 values in the field. Let's say we have GF(2^n) and have a number a∈{0,…,2^n−1}, we can represent it as a vector in the form of a polynomial:

a=a0+a_1 x+a_2 x²…a_{n−1} x^{n−1}

If we use a_n∈{0,1}, this is exactly the same as representing a binary number modulo 2^n. In this, x^n represents bit position n and a_n is the value of the bit at position x^n. If a bit is a zero at a given position, it will be not included in the polynomial equation.

First, let's talk about modulo-2 operations. For this, an addition is:

0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1 =0 (an EX-OR gate)

and for multiply we have:

0*0 = 0, 0*1 = 0, 1*0 = 0, 1*1 =1 (an AND gate)

So, 1011 can be represented by x³+x+1 and 1010 is represented as x³+x. We can then perform arithmetic operations on these polynomial values. So, to add two values of 1010+1100 we can represent this as (x³+x)+(x³+x²) and which is x²+x as we are using modulo 2 addition, and where x³+x³=0. With modulo 2 addition, 0+0=0, 0+1=1, 1+0=1, and 1+1=1.

An example of Galois Fields is within AES (Advanced Encryption Standard) and which uses a finite field GF(²⁸). With AES we operate on bytes (8 bits) in the form of b_7 b_6 b_5 b_4 b_3 b_2 b_1 b_0 and which are operated on a a polynomial of b_7x⁷+b_6x⁶+b_5x⁵+b_4x⁴+b_3x³+b_2x²+b_1x¹+b_0.

Oh, and we don't have prime numbers any more, we have irreducible polynomials or primitive polynomial, and which are polynomials that cannot be factorized into polynomial factors.

https://asecuritysite.com/gf/gf2

This operatives in a similar way to our (mod p) operation, and where we can reduce a result into the group, and just take the remainder from a division.

A few examples

Let's take a few examples to illustrate this.

Example 1. For a=x²+x+1 (7–111b) and b=x+1 (3–011b) with a primitive of x⁴+x+1 (GF(2⁴)), for addition we get x² (4–100b), and for multiplication we get x3+1(9–1001b):

Add=(x²+x+1)+(x+1)=x²

Mult=(x²+x+1)×(x+1)=x³+x²+x²+x+x+1=x³+1

As we are using modulo 2 addition, then x+x=0 and x²+x²=0. As the power of the multiplication is not greater than x⁴ and above, there is no need to divide by the primitive polynomial. The following is a sample run:

a: 1x^2 + 1x + 1b: 1x + 1b^{-1}: 1x^3 + 1x^2 + 1xp: GF(2^4) [1, 0, 0, 1, 1]Add: 1x^2Subtract: 1x^2Multiply: 1x^3 + 1Divide: 1x^3 + 1x^2

For the division, we determine the inverse of b and then multiply by a. In this case we have a×b^{−1} = (x²+x+1)×(x³+x²+x)=x⁵+x⁴+x³+x⁴+x³+x²+x³+x²+x=x⁵+x³+x. As we have a higher power that the field, we now need to divide by the primitive (x⁴+x+1) and get the remainder:

__x______x^4 + x+1 | x^5+ x^3 + x x^5 + x^2 + x -------- x^3+ x^2

This the result of the divide is then the remainder value of x³+x². You can try the example here.

Example 2. For a=x³ (8–1000b) and b=x²+1 (5–101b) with a primitive of x⁴+x+1 (GF(²⁴)), for addition we get x³+x²+1 (13–1101b), and for multiplication we get x³+x²+x (14–1110b).

Add=(x³)+(x²+1)=x³+x²+1

Mult=(x³)×(x²+1)=x⁵+x³

Now we divide x⁵+x³ by the primitive (x⁴+x+1) and get the remainder:

__x______x^4 + x+1 | x^5+x^3 x^5 +x^2+x -------- x^3+x^2+x

Thus the result of the multiplication is the remainder of x³+x²+x.

a: 1x^3b: 1x^2 + 1b^{-1}: 1x^3 + 1x + 1p: GF(2^4) [1, 0, 0, 1, 1]Add: 1x^3 + 1x^2 + 1Subtract: 1x^3 + 1x^2 + 1Multiply: 1x^3 + 1x^2 + 1xDivide: 1x^2 + 1x + 1

You can try the example here.

Example 3. For a=x³+1 (9–1001b) and b=x²+1 (5–101b) with a primitive of x⁴+x+1 (GF(2⁴)), for addition we get x³+x² (12–1100b), and for multiplication we get x³+x+1 (11–1011b).

Add=(x³+1)+(x²+1)=x³+x²

Mult=(x³+1)×(x²+1)=x⁵+x³+x²+1

Now we divide x⁵+x³+x²+1

by the primitive (x⁴+x+1) and get the remainder:

__x______x^4 + x+1 | x^5+ x^3+x^2 +1 x^5 +x^2+x -------- x^3+ x +1

Thus the result of the multiplication is x³+x+1 (11- 1011b).

a: 1x^3 + 1b: 1x^2 + 1b^{-1}: 1x^3 + 1x + 1p: GF(2^4) [1, 0, 0, 1, 1]Add: 1x^3 + 1x^2Subtract: 1x^3 + 1x^2Multiply: 1x^3 + 1x + 1Divide: 1x^3 + 1x^2

You can try the example here.

Example 4. For a=x²+x+1 (7–0111b) and b=x³+1 (5–1001b) with a primitive of x⁴+x+1 (GF(2⁴)), for addition we get x³+x²+x (14–1110b), and for multiplication we get x³+x (11–1010b).

a: 1x^2 + 1x + 1b: 1x^3 + 1b^{-1}: 1xp: GF(2^4) [1, 0, 0, 1, 1]Add: 1x^3 + 1x^2 + 1xSubtract: 1x^3 + 1x^2 + 1xMultiply: 1x^3 + 1xDivide: 1x^3 + 1x^2 + 1x

You can try the example here.

Example 5. For a=x²+x (6–110b) and b=x⁴+x²+1 (21–10101b) with a primitive of x⁶+x⁵+x⁴+x³+x²+x (GF(2⁸)), for addition we get x⁴+1x+1 (19–10011b), and for multiplication we get x⁶+x⁵+x⁴+x³+x²+x.

a: 1x^2 + 1xb: 1x^4 + 1x^2 + 1b^{-1}: 1x^4 + 1x^2 + 1x + 1p: GF(2^7) [1, 0, 0, 1, 1, 1, 0, 1]Add: 1x^4 + 1x + 1Subtract: 1x^4 + 1x + 1Multiply: 1x^6 + 1x^5 + 1x^4 + 1x^3 + 1x^2 + 1xDivide: 1x^6 + 1x^5 + 1x^4 + 1x

With addition, there will be no need for the irreducible polynomial.

You can try the example here.

The code is:

from galois_field import GFpn# Generating the field GF(2^4)# irreducible polynomial. (in this case, x^4 + x+1)import sysa=[1,1,0]b=[0,1,0]p=[1,0,0,1,1]if (len(sys.argv)>1): a=eval("["+sys.argv[1].replace(" ","")+"]")if (len(sys.argv)>2): b=eval("["+sys.argv[2].replace(" ","")+"]")if (len(sys.argv)>3): p=eval("["+sys.argv[3].replace(" ","")+"]")try: gf = GFpn(2,p )except Exception as e: print ("Error:" ,e) sys.exit()# Generating an element in GF(2^4)aval = gf.elm(a) # x^2+x+1bval = gf.elm(b) # x# Arithmetic operationsaval + bval # 1x^2 + 1aval - bval # 1x^2 + 1aval * bval # 1x^3 + 1x^2 + 1xaval / bval # 1x^3 + 1xprint ("a:\t\t",aval)print ("b:\t\t",bval)print ("b^{-1}: ",bval.inverse())print ("p:\t",gf,p)print ("\nAdd:\t\t",aval + bval)print ("Subtract:\t",aval - bval)print ("Multiply:\t",aval * bval)print ("Divide:\t\t",aval / bval) Irreducible Polynomials

Within polynomials, the prime number equivalents are known as irreducible, as they cannot be factored. I will come back to irreducible polynomials later in this series, but for now, you can read up on them at:

https://asecuritysite.com/gf/gf2

Conclusions

And, so, you made it to the end of this podcast. If you managed to understand everything here, you deserve a crypto medal. If not — for most — you should try and read over and eventually, it will sink in — slowly at first, and then you will get bits and pieces of knowledge, and eventually, it will make sense. This is one of the reasons I love cryptography — and teach and research the field — as, every day, I learn, but my learning was so much deeper once I really understand why we did all these complex-looking things, and to get behind the maths. I hope I have not given you nightmares of school and with long multiplication and division, but if I have, I can calm you that the maths we use in cryptography is so much simpler, and where you just have to know how to count just a 0 and a 1. Life is so much more relaxed in crypto space.

In previous podcasts, I outlined the usage of discrete logarithms in the form of a=g^x (mod p). Unfortunately, we now need a relatively large prime number to make sure it is now possible to discover x from a, g and p. This slows down the creation of the discrete log value. One method which has been used to replace them in some applications is to use elliptic curve points. Later in this series, I will explain how elliptic curve cryptography actually works, but in this one, we will just look at the fundamentals of the elliptic curve points.

So what is a group in elliptic curve cryptography (ECC)? Well with this, we will map one group of points to another with a one-way function, and which should be difficult to reverse or find the method we have used to perform the mapping. As we will find, the basic operation is to either add two points in a group to create another point in the group or to double the point to get another point. With these simple operations, we should be able to perform point multiplication. The method of ECC was created independently by Neal Koblitz and Victor Miller.

So, how did I create this mapping? Well, a basic elliptic curve has the form of:

y² = x³ + ax + b

For y² = x³ + 7

If x=1, we get:

y² = 1+7

and where y is the square root of 8, which is 2.82. But, in cryptography, we only deal with integers, so we must modify this with a modular form of:

y² = x³ + ax + b (mod p)

For example, if a is zero, b is 7, and the prime is 11, we get:

y² = x³ + 7 (mod 11)

The possible points are (2, 9) (2, 2) (3, 1) (3, 10) (4, 4) (4, 7) (5, 0) (6, 5) (6, 6) (7, 3) (7, 8). e can try it, and where:

9² (mod 11) = 4 and 2³+7 (mod 11) = 4

https://asecuritysite.com/ecc/ecc_pointsv?a0=0&a1=7&a2=11

As we see, not all the points for an x-coordinate value are possible. This then leads to the order, which is the number of valid x-axis points — which is 6 in this case. W

Point double and add

In ECC, we then add points together (P+Q) or double them 2.P and get a new point. With this, it is difficult to reverse back the addition or doubling and find the original point.

For y²=x³+7 (mod 11)

The valid points are (2, 9) (2, 2) (3, 1) (3, 10) (4, 4) (4, 7) (5, 0) (6, 5) (6, 6) (7, 3) (7, 8). Now let's take a point of (2,9) and add another point. So this, we get:

https://asecuritysite.com/ecc/ecc_points_add3?a0=2&a1=0&a2=7&a3=11

P1=(2,9) P2=(2,9) P1+P2=(5,0) P1=(2,9) P2=(3,1) P1+P2=(4,7) P1=(2,9) P2=(4,4) P1+P2=(3,10) P1=(2,9) P2=(6,5) P1+P2=(4,4) P1=(2,9) P2=(7,3) P1+P2=(3,1)

and so we see when we do a point add, we always get another point on the curve, but where it is difficult to reverse back to the points which resulted in this point.

Multiplying points

So, can we multiply points in an efficient way? Let's say we have G, and want to add it to itself n times. We could represent this as n.G. For this, Peter Montgomery created a method known as the Montgomery Ladder.

The basic method is:

N ← P Q ← 0 for i from 0 to m do if di = 1 then Q ← point_add(Q, N) N ← point_double(N) return Q

For a=100 we have a binary value of 1100100:

• 1100100, thus we double the point (N=2G).
• 1100100, thus we double the point (N=4G).
• 1100100, thus we add the point (Q=4G), and then double the point (N=8G).
• 1100100, thus we double the point (N=16G).
• 1100100, thus we double the point (N=32G).
• 1100100, thus we add the point (Q=4G+32G=36G), and then double the point (N=64G).
• 1100100, thus we add the point (Q=36G+64G=100G), and then double the point (N=128G).

The result is then Q=4G+32G+64G=100G. Overall, the great advantage of this method is that we will always take the same time to compute the answer, no matter the size of the value of n. This is useful, as some cryptographic operations leak information from the time they take to compute the result. The only problem here is that the double point and point adding will have a different amount of time to compute than just the point double, and where Eve could determine if there was a 0 or a 1 in the value of n.

https://asecuritysite.com/ecc/ecc_kr2

Public key encryption

So how is this used in public key encryption? We first pick a base point (G) on the elliptic curve. For our example, we could pick (2,9). Next, we then pick our private key (sk). Our public key is then pk=sk.G, and where G is added to itself sk times. Our private key is thus a scalar value, and our public key is an elliptic curve point. We use this in terms of digitally signing a message, and where the private key (sk) is used to create a digital signature, and the public key validates it. The most popular methods for this are ECDSA (Elliptic Curve Digital Signature Algorithm and EdDSA (Edward Digital Signature Algorithm). I will explain these more in a future podcast.

Conclusions

And, so, for our elliptic curve, we don't always have a valid (x,y) point, but for our Weierstrass curve, sif we do, we end up with two y values for every x coordinate. With our points, we conduct two simple operations, a point addition and a point doubling.

A fundamental element in cryptography is the mapping of one group to another and then being able to map back again. In this, there should be no confusion about the mapping and where it should be deterministic in the mapping — that is, no matter how many times we do it, we will always create the same mapping. Obviously, we can add some randomisation into the process, but with the same randomization, we always get the same mappings.

In the previous podcast, I showed how a group of A={1,2,3,4} will map to B={2,4,3,1} using a mapping of b=g^a (mod p). We see that every element of A has a one-to-one mapping from A to B. We then aim to have a mapping back from B to A, and recover the original value.

Arithmetic operations

And, so, encryption (the mapping of A to B) can become a mathematical operation, and then where the decryption (the mapping of B to A) is basically just the reverse of our encryption process. And, so, remember those puzzles as a child.

Think of a number. Now add 10 and double it. Take away 7. Add 5, and half it. The answer is 9. Of course, this is a trick, and where we get:

[(2(x+10)-7+5)/2]-x =[(2x+20–7+5)]-x = [(2x+18)/2 ]-x= [x+9]-x = 9

For this, we are basically just reversing back the method we quote in the track. And so, for encryption, we could multiply by 9, and add 14 to get our cipher value. To decrypt, we would reverse the operations so that we subtract by 14 and then divide by 9. But, in cryptography, we have a finite field in our group and thus use the (mod p) operation to constrain our integers. Luckily, all our arithmetic operations still work if we use the modulo of a prime number.

Adding and subtracting

Let's try to add, with x=8 and y=12, and use a prime number of p=11.

If we do: (x+y) (mod p) is it the same as x (mod p) + y (mod p). And, so:

8 (mod 11) + 5 (mod 11) = 13 (mod 11) = 2

Now we will try:

(8+5) (mod 11) = 13 (mod 11) = 2

So can we now subtract b from the result?

2–5 (mod 11) = -3 (mod 11) = 8

Thus if we had an operation to add to values in a group and then reverse them. This goes for modulo multiply and then divide.

Multiplying and divide

Now let's try to multiply and divide. For this, we will multiply our values by four modulo 5. This will get:

>>> (1*3)%53>>> (2*3)%51>>> (3*3)%54>>> (4*3)%52

We ignore the zero for the set in A, as we will always get the same result. Thus we map {1,2,3,4} to {3,1,4,2}. Now we need to divide by three modulo 3. For this, we create the inverse mod of the value and then just multiply. This is basically:

a/b (mod p) = a* b^{-1} (mod p)

Basically, it is the value of x which will make this true:

b.x (mod p) = 1

This x is thus the multiplicative modular inverse value of b. So, let's find the inverse of 3 (mod p):

>>> pow(3,-1,5)2

Note that the pow(x,y,p) function is x^y (mod p). Thus to divide by 3 (mod 5), we multiply by 2. Let's try it:

>>> (3*2) % 51>>> (1*2) % 52>>> (4*2) % 53>>> (2*2) % 54

and so we get our original values back. Thus we use an inverse mod to reverse a modulo multiplication.

Exponentiation

And, so, we can see that adding, subtracting, multiplying and dividing work with the modulo operations. Let's try exponentiation. For this, we can have:

b = a^x (mod p)

If we try x=3 and p=5, we get:

>>> (1**3) % 51>>> (2**3) % 53>>> (3**3) % 52>>> (4**3) % 54

Thus {1,2,3,4} maps to {1,3,2,4}. But what about the reverse? Well, we need to use an inverse log modulo p function. With this, as in the RSA (Rivest Shamir Adleman) public key method we find a value for a^x (mod p) so that:

x*y (mod PHI) = 1

and where PHI is (p-1). Now we compute:

>>> pow(3,-1,4)3

So we can go ahead and now reverse and find the inverse log for {1,3,2,4} (mod 5):

>>> pow(1,3,5)1>>> pow(3,3,5)2>>> pow(2,3,5)3>>> pow(4,3,5)4

And, so, we have reversed our modulo logarithm. Overall, the magic of PHI is at the core of the RSA method and where we can reverse the exponentiation operation. For this, we have a cipher of:

C= M^e (mod N)

and then can reverse with a value of d which is computed from:

d = e^{-1} mod PHI

and where PHI is (p-1)(q-1). We recover the message with:

M=C^d (mod N)

In this case, we actually have two prime numbers (p and q), and which are multiplied together to give the modulus (N).

Conclusions

And, so, all we need to constrain our mathematical operations on our groups is the (mod p) operation.

The problem with cryptography is that many miss some fundamental knowledge that will allow them to fully understand the key operations that are used. So, in this series of blogs, I try and explain some of the core concepts that secure our online world. Every single time that you connect to the Internet, the privacy and trustworthiness of your connection are dependent on some magical cryptographic operations.

In our world of numbers, we have N (natural numbers — positive or negative integer values), Z (integers), R (real numbers) and C (complex numbers). for this. Natural numbers can go from minus infinity to plus infinity, while integers constrain these into a ring. A ring might be from 0 to 16, and the 17 goes back to 0, and so on. If we go to -1, that is 16, -2 is 15, and so on.

For cryptography, we use the Z double-struck or blackboard bold symbol, where we typically define a group of numbers.

For this, we represent Z_n as the numbers from 0 to n-1. So, Z_7 is {1,2,3,4,5,6}. There is another group we use; the multiplicative group of integers modulo n Z_n*. This excludes the values which are a factor of n.

Z_7 will be {1,2,3,4,5,6}

Z_{12}* will be {1, 5, 7, 11} [here]

[Note: In the podcast, I said Z_16* and which will be: {1, 3, 5, 7, 9, 11, 13, 15}. 16 is 2x2x2x2, so any value with a factor of 2 in it will not be included. I will outline this in a future episode.]

So a group is basically a set of integers, and where we map from one group to another one. If we think about two sets A and B, and then create a mapping between the numbers in A to B, and vice-versa. For encryption, we want a 1-to-1 mapping from every value in A to B, and then for us to be able to reverse back from B to A.

So, if we have a set of numbers of A={1,2,3,4} we might map these to B={2,4,3,1}. If we have a value of 1 in A, it will map to a 2 in B. Then, in B, we would map back from 2 to 1. In cryptography, we typically want to make it easy to go from A to B (encrypting), but difficult to go from B to A (decrypting) — unless we know a secret.

In this example, I have used a discrete logarithm mapping with a base generator of g and a prime number:

b=g^a (mod p).

For the mapping of {1,2,3,4} to {2,4,3,1}, I have used g=2, and a prime number of 5.

b = 2¹ (mod 5) = 2 (mod 5) = 2 b = 2² (mod 5) = 4 (mod 5) = 4 b = 2³ (mod 5) = 8 (mod 5) = 3 b = 2⁴ (mod 5) = 16 (mod 5) =1

This will be cyclic, and where {1,2,3,4,5,6,7,8} will map to {2,4,3,1,2,4,3,1}. For this, we have constrained within a finite field of between 0 and 4 (or p-1).

We can see that this gives us a 1-to-1 mapping for each of the elements of our first set to the other set. Every value in B can be reversed back to its original value in A.

To reverse, though, we would need to compute the inverse log of the value in B for mod p — this is not so easy:

a =log_g(b) (mod p)

And this is the core difficulty of the discrete logarithm problem. It is this problem that secures the Internet.

To show you the difficulty of this, if I use a prime number of 2²⁵⁵-19 and a g value of 2. You will find it extremely difficult to find the x value I have used for:

b=25446473684081445734643481619349383496577344937808306324243206897292518839288

If you are interested, the answer is a=431342352456346734652345427573451341234132414341365756845234234234523

In Python, here's the solution:

>>> a=431342352456346734652345427573451341234132414341365756845234234234523>>> p=2**255-19>>> g=2>>> b=pow(g,a,p)>>> print (b)25446473684081445734643481619349383496577344937808306324243206897292518839288

So, watch out for the next podcast…

How did you get started in this industry?

What are the three key tech/software tools that you depend on the most?

What is your favouriate book or podcast?

What is the most important thing you have learned in your career?

What advice would you give your younger self?

Who inspires you?

Steve is a Professor of Cyber Security in the School of Computer Science at the University of Nottingham, as well as an Adjunct Professor at Edith Cowan University in Western Australia and an Honorary Professor at Nelson Mandela University in South Africa. He is also the Chair of Technical Committee 11 (Security and Privacy Protection) within the International Federation for Information Processing, as well as a board member of the Chartered Institute of Information Security and chair of the academic partnership committee.

His main research interests are broadly linked to the intersection of human, technological and organisational aspects of cyber security. Within this, specific themes of interest include the usability of security technology, security management and culture, cybercrime and abuse, and technologies for user authentication and intrusion detection. Related to this, he has authored over 330 papers in refereed international journals and conference proceedings, as well as various books, chapters, and professional articles.

https://www.nottingham.ac.uk/computerscience/People/steven.furnell