ASecuritySite Podcast

Blog: https://medium.com/asecuritysite-when-bob-met-alice/a-soft-target-are-higher-education-infrastructures-at-risk-4ff323fd73c5

Academia was one of the first infrastructures to build and use the Internet — in fact, they built ARPANET and which morphed into the Internet. And so, you will find that they often have privileged IP address ranges, such as for Class A or Class B. With this, when IPv4 address ranges were initially given out, universities and research organisations were granted large address spaces to allocate to their growing networks. No one, at the time, could have ever envisaged in how much the Internet has grown since then. To make things easy, nearly every computer that was allocated a public address could be connected to directly — these were routable Internet addresses. To overcome these direct connections, firewalls filtered data packets and tried to stop malicious access.

We might call this the "Happy Phase" of the Internet, where it basically interconnected trusted organisations and where there was no real concept of many people outside this trust circle having access to a computer. It was a new frontier in technological development and seemed to be a nice way to send emails between academics and researchers and to showcase their latest research work.

By a public address, we have the concept that it is possible to route data directly to a computer. As you connect to this article, you are likely to be using a non-routable IP address, which is hidden between a NAT (Network Address Translation) router. These privileged academic address spaces supported public IP address spaces for thousands or even millions of hosts — and where a Class A IP address can allow over 16 million computers to have a public IP address.

The University of California, Berkley, for example, has an IP address and subnet of 104.247.81.71/8, and where 104.0.0.0 is the network address, and where 24 bits in the address can be used for subnetworks and hosts. This means that the host part can be used to create subnetworks with an extension of the subnet field. Ultimately, a Class A address can give up to 16,777,216 publicly addressable hosts. And, so, while most organisations put their computers in private address spaces (though NAT), universities had enough IP addresses to allow many computers to be publicly addressable.

In fact, at one time, an academic's desktop computer was likely be allocated a public address and could thus be directly contacted. And, so, as long as the computer was powered on, it could be addressable. Along with this, a log of any sites visited would leave a trace of the public IP address. In fact, it was all too common to add a DNS entry of Bob's computer as "Bob.uni.edu". But, this was all created in a time of little concern about cybersecurity, and it allowed academic infrastructures to grow dynamically — and under their own control.

This was all set up before any real concept of requiring cybersecurity — as the networks were often just used to interconnect networks. So while other infrastructures have closed themselves to external threats, universities — in places — can still support legacy applications and have security support which ends after the working day.

I have observed the rise of the SOC (Security Operations Centre) in the finance industry — in fact, many of our graduates go into jobs that relate to this. I've also toured many of the SOCs in Glasgow and Edinburgh and love to see the fusion of data from inside and outside the companies. Basically, these companies had to move from being a Monday to Friday, 9am-5pm company to looking after security 24x7.

But what about Higher Education (HE) as a sector? Well, I might be wrong, but higher education has not adopted the concept of 24x7 SOCs, and at 5 pm, many networked infrastructures hand over to support staff. There is very little in the way of sharing security resources across HE, too. Like it or not, our adversaries don't work 9–5pm (GMT), and are most likely to be on a different time zone in the world.

And, so, we see the University of Manchester and the University of the West of Scotland (UWS) being subject to a cyber attack in the last few weeks, and this could be the start of a targeted offensive against network infrastructure with weaker support for security. The attack on the University of Manchester was part of a vulnerability around the usage of the MOVEIt protocol:

https://medium.com/asecuritysite-when-bob-met-alice/the-moveit-zero-day-the-payroll-hack-dd4e7ceaeb92

The attack on the UWS site happened around 6 July 2023, and now it is suspected data from the breach where it is reported that the ransomware gang of Rhysida [here] is selling breached data to the highest bidder for 20 bitcoins (£450,000):

The site went down for around a week, and it affected a range of internal systems. At the current time, it is thought that the breached data includes bank details and national insurance numbers, along with internal documents from the university. Presently, there is no real information on whether these documents are real or not.

The breach happened around the first week in July 2023, and when the UWS site started to show the message of:

At first sight, this could be a standard domain take-over, and where the HTTPs certificate is valid:

But, with a lookup, we see that the domain name has been parked at 3dqkz9i.x.incapdns.net:

Overall, Incapsula is a cloud-based hosting company — it may be that the university is using the cloud provider for their hosting. Generally, it is not recommended to actually log into the site (even though the password hint is 'Google'), as the main page seems to have a redirected site on the redirected site:

Generally, there is a sign of the usage of WordPress, and which may be used to deliver the UWS Web pages (wp-content is a typical folder used to store digital content on a Word Press site) — this might point to a WordPress site take-over:

If we go to the Way Back engine, the last recorded site archive was on 1 July [here]:

Overall, the HTML is there is signs of WordPress being used:

If we try some of the links above, we get:

Academic information infrastructures have grown independent of each other — and were a key part of building the Internet. Those, though, were the "nice" days, but where we have massively grown our digital footprint. The exposure is now massive, especially with the rise of SaaS, and where many universities use third-party applications for contacts and HR systems. We need to move into a world in which shared cybersecurity and setting up 24x7 SOCs for universities is a must … as it is for most other sectors.

I believe that university security teams should work together, and merge resources for defence, and bring in companies who are well used to running SOCs in the finance sector. At least, every institute should look at running SOC on the basis that we would see in the industry — as the data contained in the network — and the risk to student's education — is too great a risk. To me, the University of Manchester and UWS data breaches are just the start of a targeted offensive against softer targets. And the ability to recruit and keep cybersecurity staff in academia is going to be a major problem.

Related blog post: https://billatnapier.medium.com/cryptography-fundamentals-commutative-encryption-19ba4c4c2173

Introduction

What's at the core of cryptography? Well, the simple EX-OR holds a special place, as we can do not lose any information when we apply it. For a bitwise operation of 0 EXOR 0 gives 0, 0 EXOR 1 gives 1, 1 EXOR 0 gives 1, and 1 EXOR 1 gives 0.

And, so, cryptographers dream of the perfect cipher. And that cipher is a one-time pad. Basically, we generate a one-time use key for our plaintext, and then EX-OR them together, and then just EX-OR again with the same key and we will get our plaintext back. Unfortunately, we can only use it once and need to generate another one. So, let's see if we can generate something similar but just use the simple XOR method for our encryption and decryption.

In the Tor (The Onion Router) network, data is encrypted with a key from each of the Tor routing nodes. Thus, if we have three nodes of A, B and C, with A as the entry node and C as the exit node. For this, the user will generate a separate key for each node to use and encrypt with the key of A, then the key of B, and then the key of C. The encrypted data is passed to A, and which will decrypt with its key, and pass the encrypted data onto B, and who will decrypt with its key. Finally, C will decrypt with its key, and the data will be decrypted. This protects the data as it is routed. But we have to remove the keys in the reverse order they were applied. One way to do this is with commutative encryption.

When I worked as an electrical engineer, we had a hasp to isolate the electric power on a device we were working on:

With this, each person who was working on the equipment, would put on their own padlock, and where we could not put the power back on, until all the padlocks had been taken off. The padlocks could be put on in any order, and taken off in any order, but there was no way to putting the power back on, until everyone had taken their padlock off.

So how could we do this with data. Let's say that Bob, Alice and Carol want to apply their "data hasp", so that the data cannot be revealed until they have all taken off their padlock. Well, with symmetric key block ciphers, such as AES, we cannot do this, as we must decrypt in the reverse order of they keys being applied:

To encrypt: Bob → Alice → Carol … and then to decrypt: Carol → Alice →Bob

There are ways to do it with RSA, such as with SRA [here], but these methods significantly reduce the security of the process. The solution is to use a stream cipher, as we basically just X-OR the data when we are encrypting, and then X-OR again with the same key when we decrypt. We can apply multiple keys to the data, and in any order and it will always decrypt properly once we have applied all the keys.

What we need with commutative encryption is to have an encryption string which is the same length as the data string. To make the encryption string, we can use an XOF (eXtendable-Output Functions) and where we can create a hash value of a given size. For this, rather than the fixed hash of SHA-3, we can use the SHAKE. Or with With BLAKE2b we have an XOF of BLAKE2XB, and for BLAKE2s we have an XOF of BLAKE2XS. We can then basically have a secret passphrase, and which generates an output which matches the length of the plaintext. Another method we can use, is to generate an pseudo infinitely long encryption key which is the same length as the plaintext — in the same way that a stream cipher works.

With the ever increasing number of breaches, we are moving to a world where companies should not hold any personally sensitive information, as it is just too risky. So how could we create a trustworthy system, where someone can show up with a ticket, and where we can trust it, without actually revealing any personal information about where the person has booked their seat?

So how can we generate a receipt of the booking, but not give away your identity, or the details of the booking? Let's take an example of booking a seat in a theatre at the festival, and how your privacy can be respected, but where the theatre will trust the ticket.

Let's say there are 100 seats in a theatre, and I want to book one of them, but I don't want the theatre company to know which seat I've booked, or my identity. I also want a receipt of purchase that they can verify my booking. One way would be to get a trusted agent to look after the bookings, but I don't trust them either. So how can we do this?

Well it can be done with commutative encryption.

The steps would be:

• Initially the theatre company generates 100 receipts for each of the seats, and then encrypts them with its public key.
• Next when I want to make a booking they send me the encrypted receipts that they have left, and I select one at random, and then encrypt it with my public key.
• I send them all back, including the one I've encrypted.
• The theatre checks to see which one has been changed, and then decrypts it with its private key, and sends it back to me.
• I decrypt with my private key, and I can now view the receipt for my booking, and the theater company cannot determine which seat I have, but I will have the receipt of my booking.

So here is an example where the theatre encrypts all the seats with its key, the person then selects one, and encrypts with their key, and sends them all back again. Then the theater decrypts the one that has changed, and sends it back for the person to decrypt, and we have a booking. The theatre thus does not know who has booked the seat:

ChaCha20 is a stream cipher, and where we created pseudo infinitely long encryption key, and the just XOR it with the plain text.

With commutative encryption, we can decrypt with the keys in any order. Normally we would encrypt with Bob's key and then encrypt with Alice's key, and then we must decrypt with Alice's key and then Bob's. In commutative encryption, we can decrypt in any order.

With a stream cipher, we can automatically apply commutative as we basically just EX-OR with the key stream. In the following we use Go code, and where Bob encrypts, Alice encrypts, Bob decrypts, and then Alice decrypts [here].

And a sample run [here]:

We can easily extend the method to Carol, Trent, and so on. In my simple example I have used the same nonce for Bob and Alice, but in real life they would use different values, and these would be random for every transaction.

NIST chose Keccak as the standard for SHA-3. But, it's all a bit confusing, as there are two main versions of this: Keccak and SHA-3. Many systems, such as Ethereum have adopted Keccak, while others go for SHA-3. The only real difference between them is a difference in the padding of data. An eXtendable-Output Function (XOF) produces a bit string that can be of any length. In fact, we can create an infinitely long bit string, if required. The main methods are SHAKE128, SHAKE256, BLAKE2XB and BLAKE2XS. With the SHA-3 hashing method, we have four different cryptographic hashing methods (SHA3–224, SHA3–256, SHA3–384, and SHA3–512) and two XOF functions (SHAKE128 and SHAKE256).

With commutative encryption, we can decrypt with the keys in any order. Normally we would encrypt with Bob's key and then encrypt with Alice's key, and then we must decrypt with Alice's key and then Bob's. In commutative encryption, we can decrypt in any order. While our symmetric key block ciphers cannot be made commutative, we can use stream ciphers, as they perform an EX-OR function. In this example we will use the SHAKE128 or SHAKE256, and generate Bob and Alice's key.

https://asecuritysite.com/commul/comm_stream

With maths, operators such as multiplication are commutative, such as:

In encryption, most operations are non-commutative, so we need to modify the methods. One way is to use RSA, but generate two keys which have shared p, q and N values. So we generate Bob and Alice's keys using the same two prime numbers (p and q), so that they share the same N value (modulus).

So let's start with Bob:

The calculation of n and PHI is:

We need to make sure that our encryption key (e) does not share any factors with PHI (gcd(PHI,e)=1). We can select e as:

Next we can calculate d from:

The answer is 29 [Solve]

Now for Alice. We have:

We can select e as (and should not share any factors with PHI):

Now we must solve:

For this we get 31 [Solve]

Alice's keys are then:

An example of this is here:

https://asecuritysite.com/commul/comm2

As we have seen, commutative encryption allows us to decrypt in any order. For this we can use Massey–Omura Cryptosystem and generate encryption keys which share a prime number.

One classic patent for commutative encryption was written by James Massey and Jim K. Omura created the Massey–Omura Cryptosystem in 1982 [1]. It took over three years to be assigned and was assigned to Omnet Associates [here]:

It uses exponentiation in the Galois field GF(2^n) for both the encryption and decryption functions. In this, if we have a message of M, the encryption is:

and

This are operated on with the Galois field. For this we define e within:

and we make sure that e does not share a factor with 2^n-1 using:

The decryption exponent d is defined as:

This works because the multiplicative group of the Galois field GF(2^n) has order 2^n−1, and where Lagrange's theorem defines that m^{de}=m for all the values of m in GF(2^n). The coding is here [link]:

A sample run is [link]:

One of the advantages of the Massey–Omura Cryptosystem is that we can apply commutative encryption. In this way, Bob may have keys of (e_b,d_b) and Alice has keys of (e_a,d_a). We can then apply the keys in any order, such as encrypting with e_a and then encrypting with e_b, and where we can then decrypt with d_a and then decrypt with d_b, or decrypt with d_b first and then decrypt with d_a (as we would normally do).

To encrypt:

Cipher=E(a_b,E(e_a,M))=E(e_a,E(e_b,M))

To decrypt:

E(d_b,E(d_a,Cipher))=E(d_a,E(d_b,Cipher))

Here is an example:

https://asecuritysite.com/commul/massey2

Communative encryption is a great way of applying multiple keys to encryption data, and then for them to be removed in any order that is required. It is a little like how data is encrypted in the Tor network, but that requires the keys to be removed in the reverse order they were applied. In a future podcast, I will explain how the Tor network works.

Blog: https://medium.com/asecuritysite-when-bob-met-alice/can-privacy-and-traceability-exist-together-tracing-keys-and-jurisdictions-bfc395d502a

Introduction

Privacy and traceability are two sides of the same coin, and where the coin will never land on its side. If you want privacy in a transaction, you have to hide the payer and payee and the transaction value. All that needs to happen is that there is proof that the payer has enough currency to pay the payee. We can do this with a range proof — so that Bob can show that the sum of his previous transactions minus the current one is greater than zero. But, this stops any traceability and stops investigators from investigating the trail of an illegal transaction. It's a dilemma that can keep cybersecurity professionals awake at night and where a few bad apples can spoil the whole bunch.

But, if we add traceability — such as in Bitcoin — we remove the privacy aspect, and if someone links your Bitcoin address to you and the others you trade with, they will be able to see all your transactions. "Ah, I see", they might say, "That Bill has just bought a ticket for a bus journey in Edinburgh at 10:03 am".

Along with this, we have different requirements in different jurisdictions and where we might want to limit the investigator power in one jurisdiction to others.

For this, John Gilmore — one of the original Cipher Punks — wrote:

"We are literally in a race between our ability to build and deploy technology, and their ability to build and deploy laws and treaties. Neither side is likely to back down or wise up until it has definitively lost the race"

And, so, the tension between strong cryptography, which protects privacy, and the ability to monitor and investigate remains as open as ever. In the UK, the Online Safety Act could aim to insert backdoors in cryptography in order to monitor communications.

So, is it possible to keep things private but also make them traceable? For this, a new paper outlines the TRCT (Traceable Anonymous Transaction Protocol for Blockchain) protocol [1]:

The focus of the paper is on the anonymous cryptocurrencies such as Monero, Dash and ZCash. It uses an Extractable Proof of Knowledge (EPoK) to produce a Zero Knowledge Proof (ZKP) for a transaction. This can then be added to the RingCT method of anonymity to produce traceable transactions for the participants and the amount transacted. The transaction, though, is still kept anonymous.

The paper pinpoints the usage of Monero in a number of crimes, such as for the Wannacry ransomware attack and where the adversaries converted their Bitcoin rewards into Monero tokens [here], and which has not been since been traced. This problem has become so difficult for law enforcement that privacy-protecting cryptocurrencies have been banned in Canada, South Korea and Australia.

An overview of TRCT is defined in Figure 1. With this, we have a miner which collects broadcasted transactions, and creates a consensus with other miners. An Authority is then responsible for linking account addresses and transactions and which can trace anonymous account addresses of the actual payer and payee and resolve the transaction amount.

For TRCT, the payer generates a long-term key pair and then creates a one-time address (Figure 1). This can then be sent to the payer. The transaction is then anonymised for the payer address, payee address and transaction value using the Ring CT protocol, and which integrates the EPoK scheme. The miner then receives this and checks that it is valid and that the payer has enough currency in their account to make the payment. Next, the miner will check the EPoK so that it can be traced by the authority — and without discovering the secret details in the transaction. The authority can then trace the hidden content in the transaction (Figure 2).

While applied in RingCT, the TRCT can be generally applied to any permissionless and permissioned blockchain, as it does not affect the underlying logic of the blockchain. In this, a trusted authority creates a tracing key and publicises its public key to the miners and whether these miners may be enabled or not for the integration of EPoK. In a permissioned blockchain, there are typically fewer nodes that create the consensus, and where it is thus easier to broadcast and update the tracing key. Overall, the authority is then used to oversee all the transactions, and decide whether there are illegal transactions, and also trace them.

The control of the tracing key can then use attribute-based encryption to control its usage and using threshold-based sharing to control the usage of the key. For example, the FBI, CIA and GCHQ could agree on a 2-from-3 share approach, where two agencies have to come together to regenerate the tracing key. This approach allows for different jurisdictions to generate their own tracing key and where they cannot trace within any other jurisdiction. The addition of tracing tags also allows the tracing of high-value transactions.

Next, let's cover ring signatures and RingCT.

And so there has been a leak of information at the White House. Donald Trump calls in his Cyber Security leads and tells them, "I know one of you leaked the information, but I can't tell which one". How can Donald tell that one of his leads has leaked the information but does not know which one? Well, this can be achieved with a ring signature, and which provides anonymity, unforgivably and collusion resistance.

A ring signature is a digital signature that is created by a member of a group which each has their own keys. It is then not possible to determine the person in the group who has created the signature. The method was initially created by Ron Rivest, Adi Shamir, and Yael Tauman in 2001, and in their paper, they proposed the White House leak dilemma.

In a ring signature, we define a group of entities who each have their own public/private key pairs of (P1, S1), (P2, S2), …, (Pn, Sn). If we want an entity i to sign a message (message), they use their own secret key (si), but the public keys of the others in the group (m,si,P1…Pn). It should then be possible to check the validity of the group by knowing the public key of the group, but not possible to determine a valid signature if there is no knowledge of the private keys within the group.

So let's say that Trent, Bob, Eve and Alice are in a group, and they each have their own public and secret keys. Bob now wants to sign a message from the group. He initially generates a random value v, and then generates random values (xi) for each of the other participants, but takes his own secret key (si) and uses it to determine a different secret key, which is the reverse of the encryption function.

He now takes the message and takes a hash of it, and thus creates a key (k). This key will be used with symmetric encryption to encrypt each of the elements of the ring (Ek), and then each element of the ring uses an EX-OR function from the previous element:

Each of the random values for the other participants is then encrypted with the public key of the given participant. Bob then computes the value of ys in order to create the ring (the result of the ring must equal v). He will then inverse this value to produce the equivalent private key (xs). Bob now releases the overall signature, and the random x values, along with the computed secret key. To check the signature, the receive just computes the ring and checks that the result matches the sent signature.

The basic method are:

1. Generate encryption with k=Hash(message).

2. Generate a random value (u).

3. Encrypt u to give v=Ek(u).

4. For each person (apart from the sender):

• 4.1 Calculate e=si^{Pi} (mod Ni) and where si is the random number generated for the secret key of the ith party, and Pi is the public key of the party.
• 4.2 Calculate v=v⊕e

5. For the signed party (z), calculate sz=(v⊕u)^d (mod Nz) and where d is the secret key of the signing party.

We will end up with the signature (v=Ek(u)), and which completes the ring.

The basic method involves creating Bob creating fake private keys for the other people in the ring:

The verification of the ring is then:

The major problem with the Bitcoin network is that the amount of a transaction and the sender and receiver of the funds are not private, and someone who knows someone's address can trace their transactions. This is the case because the blockchain needs to check that the sender has enough funds to pay the recipient. Thus many cryptocurrencies are looking for ways of anonymising the transaction. Ethereum, for example, uses zk-Snarks to hide identities.

One method of preserving identity was proposed by Rivest et al and used RSA encryption. Unfortunately, it is not efficient for modern systems, thus, Greg Maxwell's defined an elliptic curve method as a new way of creating the ring signature: the Borromean ring signature [paper].

The cryptocurrency Monero then adopted the method for anonymising transactions but has since migrated to a new method: Multi-layered Linkable Spontaneous Anonymous Group signature. This method hides the transaction amount and the identity of the payer and recipient [paper]. It is now known as RingCT (Ring Confidential Transactions), and was rolled out in January 2017 and mandatory for all transactions from September 2017.

TRCT provides a roadmap for the integration of tracing keys and the segmentation of rights of access. It is unlikely that we will see the implementation of this method is Monero anytime soon, but it could be applied to new methods. It is only interesting to see it applied to permissioned blockchains, and it could be useful in banking applications which require privacy but traceability.

[1] Duan, J., Wang, L., Wang, W., & Gu, L. (2023). TRCT: A Traceable Anonymous Transaction Protocol for Blockchain. IEEE Transactions on Information Forensics and Security.

Blog: https://medium.com/asecuritysite-when-bob-met-alice/did-you-buy-a-ring-doorbell-from-2015-to-2019-then-you-could-get-compensation-c8434916b2da

I know the title sounds like one of those adverts that say,

Before COVID-19, I used to demonstrate live at conferences the Ring doorbell and showcase weak practices. The video wasn't encrypted at all, and where I could easily view it. Along with this, user credentials were left unencrypted. But, after we went into lockdown, it was not so easy to give practical demonstrations, so I've not done a demo for a few years. But you will be glad to know that I'm all set up for hacks on electrical sockets, doorbells, kettles, door locks, and many other things, so if your company wants a demo, please get in contact.

Overall, I have found that for the balance between useability/ease of setup, and security, most companies go for useability/ease of setup, as they know their users are often not that technical. Now, it has been shown that there are thousands of customers of the Ring doorbell that have been affected by cyberattacks.

For this, Amazon will have to pay out $5.8 million in payments to around 55,000 customers for its weak data security practices. For this, it has been well known that some employees at Amazon had been spying on user videos:

It was also found that there was no encryption on the video streams and that credentials were sent in a plaintext format. There were also attacks on previously breached passwords or in using repeated attempts at guessing credentials. Normally, this type of practice would be defended with a lock-out policy or by monitoring password usage, and which was weakly implemented. The case was brought by the FTC (Federal Trade Commission) in a federal court [here]:

It is thought that 1,250 devices were breached with passwords, that the live stream was compromised, and that there were at least 20 cases that involved a breach of over one month. The suit outlines cases involving screaming obscenities, demanding ransoms, and threatening murder and sexual assault [here], and covers those who bought Ring doorbells between 2015 and 2019 — even if they have not been hacked. These will be used to pay for refunds for the doorbell and requires that Amazon delete all the video information gathered and any user credentials. Amazon will also have to inform the FTC about future incidents.

Along with this, the FTC reported that Amazon failed to encrypt video streams from 2016 and 2020, along with no encryption for user credentials and details, and failed to get user consent for the viewing of video streams. Also, they failed to provide adequate training for their staff in supporting the Ring doorbell. In 2021, though, Amazon finally implemented encryption and proactive monitoring on the product [here]:

Alongside this, Amazon will also have to pay $25 million for Alexa with the FTC Act and Children's Online Privacy Protection Act by retaining children's information without parental permission. Amazon will also be required to stop using geolocation, voice information, and children's voice information for any product improvement purposes.

When ease of use and usability are placed before cybersecurity, there's likely to be a storm brewing. I like Apple devices, as they seem to be able to span both sides of this. My demos for Ring, though, don't work anymore, but I've got many other things to showcase.

Overall, one bad product implementation can taint a whole brand. Amazon needs to watch that its Ring doorbell doesn't give the company a bad name, as it has its e-commerce and cloud infrastructure to look after.

A guest talk on Quantum Computing and Impact On Public Key Encryption by Professor Alan Woodward.

Related blog: https://medium.com/asecuritysite-when-bob-met-alice/mathematics-in-the-blood-the-lenstra-family-bf188c686e74 Introduction I know it's a strange question to pose, but which family has most advanced the Internet and Cybersecurity? Well, the Lenstra family has a strong claim to that title. From their Dutch roots, they have contributed so much to our modern world — both from a theoretical and a practical point of view. I suppose there's something in the nature of the Dutch that not only wants to solve real problems, but do it in a scientific way. That approach is also the beating heart of academic research — to take major problems and solve them through collaborative efforts, and where each researcher breaks solves part of the puzzle. The Internet — and in fact our modern world — has been created through the coming together of all the amazing work of researchers over many decades.

My grandfather was an electrician, and my father was one too. I suppose electrical things are in my blood. It was where I started my career, and I have always had a love for everything that relates to electrons. I must admit I gave myself a little too many electrical shocks when I was a child, as the temptation to take things apart just seemed too strong for me. And, it still amazes me that we often just take electricity — and all its applications in our modern world — for granted. Where would we be without our control of electricity and all things electrical? You certainly wouldn't be reading this article, now.

So, sometimes, there's something in our blood that defines our future careers. And for the Lenstra family that was certainly the case, and from their Dutch roots, Hendrik, Arjen, Andries and Jan Karel have become important mathematicians.

One of the most famous of the brothers for those who have studied networking is the mighty Jan Karel Lenstra (J.K. Lenstra) and whose many major breakthroughs include scheduling, local searches and the travelling salesman problem. We can thus all thank Jan for his work on routing problems, and which led to the creation of routing protocols on the Internet:

The solving of the routing problem on the Internet, allowed the Internet to scale to levels that we see now, and where we have almost instant access to information from any part of the planet. We can thank J.K. Lenstra for providing that foundation.

Arjen followed a cryptography focus for his work, including many classic papers such as those related to the factorization of polynomials and a famous paper entitled "Ron was wrong. White is right" [here]:

But, Arjen's most cited paper included his brother (Hendrik W. Lenstra Jr.) as a co-author [3]:

And, in these days of Microsoft Word and LaTeX, don't you just love the pen markup on the paper? The brothers also collaborated on another classic paper — and which included the mighty J.M Pollard [2]:

When the two brothers worked together they created some of their best work, and it was the classic Factorizing Polynomials with Rational Coefficients paper [3] that led to the Lenstra–Lenstra–Lovász (LLL) method [paper]. The paper also included mighty Laszlo Lovász [here] (who has an h-index of 109):

This will use this method — defined as Lenstra–Lenstra–Lovász (LLL) — to crack the signature, and discover the private key used to digitally sign the message. This will search for the private key that has been used to sign a message with ECDSA. In this case we will generate two signatures, and then search for a private key.

One of the most common signatures is ECDSA (Elliptic Curve Digital Signature Algorithm) and which is used with Bitcoin and Ethereum. With this, Bob creates a random private key (priv), and then a public key from:

Next, in order to create a signature for a message of M, he creates a random number (k) and generates the signature of:

The signature is then (r,s) and where r is the x-co-ordinate of the point kG. H(M) is the SHA-256 hash of the message (M), and converted into an integer value. If the k value is revealed for any of the signatures, an intruder can determine the private key using:

This works because:

and so:

and for priv:

We can then use the code [here] to implement a searching method based on LLL:

A sample run is [here]:

It is a truly fantastic paper, and well worth a read.

In December 2019, a team led by Paul Zimmermann of INRIA announced the factorization of the largest ever RSA modulus (RSA-240):

The factorization involved factorizing a 795-bit integer into its prime number factors. It caused industry experts to define that RSA would only be safe with at least 2,048-bit keys. Actually it was Arjen, in the 1990s, who was the first to crack the early RSA challenges, and managed to factorize 330 (100 decimal digits), 364, 426 and 430 bit modulus values [here]:

Hendrik W. Lenstra Jr. became a Professor at the University of Amsterdam in 1979, and then, in 1987, he appointed to the University of California, Berkeley. One of his most famous PhD students is Daniel J. Bernstein [here], who is famous for producing standards such as Curve 25119, ChaCha20 and Poly1305. In the year Hendrik was appointed to Berkley, he outlined a method to factorize integrations using elliptic curve methods [1]:

The security of several public key methods rely on the difficulty in factorizing a modulus created from the multiplication of large prime numbers. RSA is a good example of this, and where we take two large prime numbers (p and q), and multiply them to create a modulus (N). The difficulty is then to be able to find p and q, if we know N. The two core methods we can use for this factorization are the general number field sieve (GNFS) method and ECM (Elliptic Curve Method).

With his method, we define the moving from a point P on an elliptic curve to 2P. For this we find the tangent to the point P and use this to find 2P. This tangent will be defined with a slope (s) and with a gradient in the form of a/b. For this we must find the modular inverse of b. If we cannot find the modular inverse of b, a factor of N is gcd(N,b), and where gcd() is the greatest common denominator.

If our curve is y²=x³+ax+b, the slope (s) will be:

as defined in differentiation. In detail, we first pick a random point P=(x0,y0) on an elliptic curve of:

We also select a random value of A and then calculate:

For two points on the curve: P=(Px,Py) and Q=(Qx,Qy) , the slope of the line between them will be:

With this we have s in the form of a/b (modN) .

Next we define:

and using:

If Px=Qx and Py=−Qy, we define as 0 [Identity], else we calculate R=P+P=2P=(Rx,−Ry):

Here are some test runs:

• N=15 (Factor: 3 and 5 Try!
• N=6,161 (Factors: 61 x 101) Try!
• N=32,128 (Factors: 2 x 2 x 2 x 2 x 2 x 2 x 2 x 251) Try!
• N=53,421 (Factor: 3 x 17,807) Try!
• N=55,440 (Factors: 2 x 2 x 2 x 2 x 3 x 3 x 5 x 7 x 11) Try!
• N=999,999 (Factor: 3 x 3 x 3 x 7 x 11 x 13 x 37) Try!
• N=10,000,000 (Factor: 2 x 2 x 2 x 2 x 2 x 2 x 2 x 5 x 5 x 5 x 5 x 5 x 5 x 5) Try!
• N=100,001 (Factor: 11 x 9091) Try!
• N=455,839 (Factor: 559 x 761) Try!
• N=3,789,829 (Factor: 3209 x 1181) Try!
• N=7,388,399 (Factor: 3571 x 2069) Try!
• N=392,524,199 (Factor: 431 x 919 x 991) Try!

An outline of the code used is [code]:

And, so, there's something in the Dutch approach to solving real problems, and in using a scientific approach, and the Lenstra have highlight that as well as any other.

And for the factorizing of integers, the great public key methods of the past, may not scale well into the 2020s, especially as factorization becomes more powerful, and is actually beating Moore's Law. If you are interested, here are other methods for factorization:

• Difference of squares. Diffsq. This factorizes using the difference of squares method.
• Factors of integers. Factors. Determine factors of an integer.
• Pollard's ρ method (Factoring integers). Pollard. The Pollard ρ method factorises integers.
• Simplify ap (modN) Go. Simplify the a^p (modN) operation.
• Smooth numbers. Go. Outline of smooth numbers.
• Quadratic residue (mod p). Go. Outline of quadratic residue (mod p).
• Quadratic residue (mod N) and where N=pq. Go. Outline of quadratic residue (mod N) with N made-up of two prime numbers.
• Dixon. Go. Dixon Method.

[1] Lenstra Jr, H. W. (1987). Factoring integers with elliptic curves. Annals of mathematics, 649–673.

[2] Lenstra, A. K., Lenstra, H. W., & Lovász, L. (1982). Factoring polynomials with rational coefficients. Mathematische annalen, 261(ARTICLE), 515–534.

[3] Lenstra, A. K., Lenstra, H. W., Manasse, M. S., & Pollard, J. M. (1993). The number field sieve. In The development of the number field sieve (pp. 11–42). Springer, Berlin, Heidelberg.

Related page: https://medium.com/asecuritysite-when-bob-met-alice/clocks-latex-byzantine-generals-and-post-quantum-crypto-meet-the-amazing-leslie-b-lamport-b2ade4b590d7

Demo: https://asecuritysite.com/hashsig/lamport

Introduction

I write this article in Medium and with its limited text editor, but I really would love to write it in LaTeX. Before the monopoly of Microsoft Word, there were document mark-up systems such as Lotus Manuscript, and where we had a basic editor to produce publishing-ready content. The GUI came along, and all the back-end stuff was pushed away from the user. For many, this is fine, but for those whose output is focused on sharing and dissemination of research, it is often the only way to work.

In research, LaTeX is King and is a fully formed method of laying out — and sharing — research outputs. In the past few years, we have published over 100 research papers, and not one of them has been created in Microsoft Word. And for this, I thank Leslie Lamport.

In fact, ask our kids about Newton, Faraday or Einstein, and they could probably tell you something about them. But ask them about Whitfield Diffie, Shafi Goldwasser, or Leslie B Lamport, and they would probably look quizzical? Their future world, though, is probably going to be built around some of the amazing minds that built the most amazing structure ever created … The Internet.

So, I am so privileged to be an academic researcher. For me, teaching, innovation and research go hand-in-hand, and where the things I research into gives me ideas for innovation, and which I can then integrate these things into my teaching. The continual probing of questions from students also pushes me to think differently about things, and so the cycle goes on. But, we are all just building on the shoulders of true giants, and there are few larger giants than Leslie Lamport — the creator of LaTeX.

For me, every time I open up a LaTeX document, I think of the work he did on creating LaTeX, and which makes my research work so much more productive. If I was still stuck with Microsoft Office for research, I would spend half of my time in that horrible equation editor, or in trying to integrate the references into the required format, or in formatting Header 1 and Header 2 to have a six-point spacing underneath. So, for me, the contest between LaTeX and Microsoft Word is a knock-out in the first round.

And one of the great things about Leslie is that his work is strongly academic — and which provides foundations for others to build on. For this, he did a great deal on the ordering of task synchronisation, in state theory, cryptography signatures, and fault tolerance.

I really can say enough about how much LaTeX — created in 1984 — helps my work. I am writing a few books just now, and it allows me to lay out the books in the way that I want to deliver the content. There's no need for a further mark-up, as I work on the output that the reader will see. But the true genius of LaTeX is the way that teams can work on a paper, and where there can be async to GitHub and where version control is then embedded.

Overall we use Overleaf, but we're not tie-in to that, and can move to any editor we want. But the process is just so much better than Microsoft Word, especially when creating a thesis. Word is really just the same old package it was in the 1990s, and still hides lots away, and which makes it really difficult to create content which can easily be changed for its layout. With LaTeX, you create the content and can then apply whatever style you want.

Many in the research community think that the quality measure of a paper is the impact factor of the journal that it is submitted to, or in the amount of maths that it contains. But, in the end, it is the impact of the paper, and how it changes thinking. For Leslie, in 1978, his paper on clocks changed our scientific world and is one of the most cited papers in computer science [here]:

In 1981, Leslie B Lamport defined the Byzantine Generals Problem [here]:

And in a research world where you can have 100s of references in a paper, Leslie only used four (and which would probably not be accepted these days for having so few references):

Within this paper, the generals of a Byzantine army have to agree to their battle plan, in the face of adversaries passing in order information. In the end, we aim to create a way of passing messages where if at least two out of three of the generals are honest, we will end up with the correct battle plan. So why don't we build computer systems like this, and where we support failures in parts of the system, or where parts of the system may be taken over for malicious purposes? And the answer is … no reason, it just that we are stuck with our 1970s viewpoint of the computing world, and everything works perfectly, and security is someone else's problem to fix.

So, we need a system where we create a number of trusted nodes to perform a computation, and then an election process at the end to see if we have a consensus for a result. If we have three generals (Bob, Alice and Eve), we need two of them to be honest, which means we can cope with one of our generals turning bad:

In this case, Eve could try and sway Trent by sending the wrong command, but Bob and Alice will build a better consensus, and so Trent will go with them. The work can then be defined as MPC (Multiparty Computation) and where we have multiple nodes getting involved to produce the final result. In many cases, this result could just be as simple as a Yes or No, and as to whether a Bitcoin transaction is real or fake, or whether an IoT device has a certain voltage reading.

Sometime soon we perhaps need to wean ourselves of our existing public key methods and look to techniques that are more challenging for quantum computers. With the implementation of Shor's algorithm [here] on quantum computers, we will see our RSA and Elliptic Curve methods being replaced by methods which are quantum robust. One method is the Lamport signature method and which was created by Leslie B. Lamport in 1979 [here]:

At the current time, it is thought to be a quantum robust technique for signing messages. When we sign a message we take its hash and then encrypt it with our private key. The public key is then used to prove it and will prove that we signed it with our private key. The Lamport signature uses 512 random hashes for the private key, and which are split into Set A and Set B. The public key is the hash of each of these values. The size of the private key is 16KB (2×256×256 bits) and the public key size is also 16 KB (512 hashes with each of 256 bits).

The basic method of creating a Lamport hash signature is:

• We create two data sets with 256 random 256-bit numbers (Set A and Set B). These are the private key (512 values).
• Next, we take the hash of each of the random numbers. This will give 512 hashes and will be the public key.
• We then hash the message using SHA-256, and then test each bit of the hash (0 … 255). If it is a 0, we use the ith number in Set A, else we use the ith number from Set B.
• The signature is then 256 random numbers (taken from either Set A or Set B) and the public key is the 512 hashes (of Set A and Set B).

This process is illustrated below:

We can use the Lamport method for one-time signing, but, in its core format, we would need a new public key for each signing. The major problem with Lamport is thus that we can only sign once with each public key. We can overcome this, though, by creating a hash tree which is a merger of many public keys into a single root. A sample run which just shows the first few private keys and the first public keys:

In this case, we take the random number and then convert it to a string. So the SHA-256 signature of "6f74f11f20953dc91af94e15…0db03ebdf06d59556c" is 7f2c9414db83444c586c…49d9b4f03e9ba9. If can be seen that the hash of the message ("The quick brown fox jumps over the lazy dog") has a hex D value at the start, which is 1101 in binary, and we see we take from SetB [0], SetB [1], SetA [2] and SetB [3]. A demonstration is given here.

The Internet we have now built on the foundations that Leslie applied. On 18 March 2013, he received the AM Turing Award (which is like a Nobel Prize in Computer Science). At the time, Bill Gates said:

Basically, much of our computing world is still using the amazing foundation that was created in the 1970s and 1980s. We tip our hats to Diffie Hellman, Shafi Goldwasser, Ralph Merkle, Ron Rivest, Adi Shamir, and, of course, Leslie B Lamport. As a note, that while Leslie's paper on Clocks is cited over 12,000 times, the Diffie Hellman paper is cited over 19,300 times:

We really should be integrating computer science into our school curriculum, and show that it has equal standing to physics, biology and chemistry, and it will shape our future world as much as the others. Why not teach kids about public-key cryptography in the same way that we talk about Newton?

Related material

• Main page: https://billatnapier.medium.com/cryptography-fundamentals-8-rsa-rivest-shamir-and-adleman-445b91932bd0
• RSA: https://asecuritysite.com/rsa

Introduction

In August 1977, The Stranglers were in the music charts with "Something Better Change" and something really was changing, and it was something that would change the world forever. This was the month that Martin Gardner in his Scientific American column, posted a challenge of a method that has stood the test of time: RSA. It related to the work of R(ivest), A(dleman) and S(hamir) and was a puzzle on their discovery of a method which allowed two keys to be created, where one could encrypt and the other to decrypt. Their work had been based on a proposal from Whitfield Diffie and Martin Hellman on trapdoor functions that could be used to create the key pair.

In order to explain the RSA concept, Martin's provided a background the Diffie-Hellman method for which he outlined:

Overall the Diffie-Hellman method has had a good run, but it has struggled in recent years to keep up with the processing power for computers, and the millions of years of running is not quite the case in the modern area, and where the original ciphers could now easily be broken with the simplest of computers within minutes.

With the RSA method, Martin Gardner outlined:

On receipt the requesters eventually (it took over four months in many cases) received a precious piece of history (Figure \ref{fig03}).

It seems unbelievable these days, but the original methods were based on two 63-digit prime numbers that would be multiplied to create a 126-digit value:

A 256-bit number, at its maximum, generates 78-digits:

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

The 40 quadrillion years has not quite happened, and where 512-bit keys are easily broken in Cloud. If you are interested, here is a 512-bit integer value and which has 148 digits, such as:

web: http://asecuritysite.com/encryption/random2

The search for prime numbers, too, has been progressive since 1977, and by 2014, the world discovered a 17,425,170-digit prime number. The finding of prime numbers make the finding of them in the RSA method must easier.

So the RSA method has been under attack for years, from both discovering prime numbers and also in factorizing. Along with this computing power has increased massively. If think that 40 years that have passed, and take a quick assumption that computing power doubles every year then we get:

and if we get a GPU card with 4,000 processors, we take it to less than a year, and we get of few of them today into a cluster, and we crack it within one day! The FREAK vulnerability was actually caused by the limiting of RSA keys, due to US Export controls, to 512-bits.

The factorising of prime numbers too has generated methods which can quickly find the prime number factors

Once Martin had published the article, the requests for the article came rushing in, especially as the paper had not yet appeared in the Communication of the ACM. Initially there were 4,000 requests for the paper (which rose to 7,000), and it took until December 1977 for them to be posted.

Why did it take so long to get the paper published and also to send them out? Well the RSA method caused significant problems within the US defence agencies. This was highlighted in a letter sent from J.A.Meyer to the IEEE Information Theory Group on a viewpoint that cryptography could be violating the 1954 Munitions Control Act, the Arms Export Control Act, and the International Traffic in Arms Regulations (ITAR), and could thus be viewed equivalent to nuclear weapons. In even went on to say that:

The main focus of the letter was that any work related to cryptography would have to be cleared by the NSA before publication. In fact, the letter itself had been written by Joseph A Meyer, an employee of the NSA.

Joseph had already been embroiled in controversy with a proposal to fit a tracking device to the 20 million US citizens who had been associated with crime. The tag would then be used to monitor the location of the "subscriber", and to detect when they broke a curfew or committed a crime. In this modern era of GPS tracking of everyone's phones, Joseph's dream has actually become a reality, but now everyone is monitored.

The RSA team thus had a major dilemma, as many of the requests for the paper come from outside the US. Martin Hellman, who was a co-author of the Diffie-Hellman method, had already had problems with ITAR, and even decided to present thep aper himself in 1977 at Cornell University rather than the practice of letting his PhD students present the work.

His thinking was that the court case would be lengthy, and that it would damage his PhD student's studies (Ralph Merkle and Steve Pohlig), and so he stood up for academic freedoms. Initially the students wanted to present their work, but their families did not think it a good idea. Eventually though, Ralph and Steve stood beside Hellman on the stage to present the paper, but did not utter a word.

With this stance the cryptographers held ground, and hoped that a stated exemption on published work within ITAR would see them through. The worry, though, did delay the paper being published, and for the posting of the article. In reply to Meyer's letter, the IEEE stood its ground on their publications being free of export licence controls, with the burden of permissions placed on the authors:

and then additional response from the IEEE saying they put in place safeguards for the publishing of material.

The scope of the impact of RSA was perhaps not quite known at the time with Len Adleman stating:

In fact, Adleman has said that he did not want his name on the paper, as he had done little work on it, but he did insist that his name went last. Often papers, too, have an alphabet order, and if so the method could have been known as the ARS method … not the kind of thing that you would want to say to audiences on a regular basis.

Within cryptography we typically use non-negative integer values, and perform integer operations. The challenge in public key encryption is to find a method which is computationally difficult for a computer to solve, if it does not know a given secret (normally the private key). One such problem is the difficulty in factorizing a value made up of the multiplication of two large prime numbers. In RSA, we take two large prime numbers — typically at least 512 bits long — and then multiply these together to create a modulus value, (N) (often at least 1,024 bits long). From this, we then derive a public exponent (e) and a modulus. The modulus N is thus determine by multiplying the two prime numbers (p and q):

The core challenge here is that it should be extremely difficult (and costly) to determine the two prime numbers which make up N. Next we select the value of our encryption key value for the public key (e). This is selected so that N and e do not share any factors: gcd(e,PHI)=1, and where

PHI = (p-1)(q-1)

This is known as Euler's totient function.

The most typical value we use for e is 65,537 (0x10001). To produce a cipher (C), we convert our message into the form of an integer (M) and then use e and N to give:

To decrypt this, we take the cipher (C), and recover the message value using the decryption exponent (d) and the modulus (N):

To make RSA work, we then need to calculate the private exponent (d) to obey:

and where phi is:

We determine d by determining the inverse of e modulus phi:

So let's take p=11 and q=7, and pick e of 3. N will be:

N=p.q = 77

PHI is 6x10=60

We can't pick e of 3 or 5, so we will pick e=7. Now we compute the decryption exponent of

d = e^{-1} mod (PHI)

>>> pow(7,-1,60) 43

If we select a message of 19, we get a cipher of:

C=19⁷ (mod 77) = 68

Now to decrypt:

M= 68⁴³ (mod 77) = 19

Our public key is then (e,N) and the private key is (d,N). The usage of the (mod N) operation is the magic that makes this work. Unfortunately, the RSA method has suffered from performance issues as we have increased the size of the prime numbers used. Thus, if researchers can crack a modulus of 1,024 bits, they will factorize the two 512-bit prime numbers used. At the current time, a public modulus of 2,048 bits is recommended. So while a modulus of this size is acceptable within a powerful computer, devices which have limited CPU resources often struggle in creating the keys, and in the encryption and decryption process.

With the mathematical operations involved, RSA is hardly ever used for core encryption, as symmetric key methods are much more efficient in their implementation. But it is fairly efficient when dealing with relatively small data sizes, such as for a symmetric key (typically only 128 bits or 256 bits long). For this, Alice might protect a symmetric key with her public key, and whenever she needs to use it, she will decrypt it with her private key. Another area where we use RSA is to take a hash of a message, and then encrypt this with the private key. As the hash is relatively small (such as 128 bits, 160 bits or 256-bits), it is relatively efficient on the use of the computing resources.

Where public key encryption methods come in most use is within creating digital signatures, and where Bob can take a hash of a message, and then encrypt this hash with his private key. Alice can then also take a hash of the received message, and decrypt Bob's encrypted hash with his public key, and compare the values produced. If they match, she determines that it was Bob who sent the message and that it has not been changed by anyone.

In Figure \ref{fig_trust03} we see that Bob has a key pair (a public key and a private key). He takes a hash of the message and encrypts with his private key, and then appends this to the message. This and then message will be encrypted by the symmetric key that Bob and Alice share (typically this is either a long-term shared key, or has just been negotiated through a hand-shake). When she receives the ciphered message, she decrypts it with the shared symmetric key, and then takes her own hash of the message. She also decrypts the encrypted hash using Bob's public key, and then compares the hashes. As the public key and the private key work together, only the signing by Bob's private key will reveal the hash with his public key. Alice can then tell that the message has not been changed — as the hash would change if Eve has modified it — and that it was produced by Bob (and not by Eve pretending to be Bob). Obviously, we now have a problem in how we get Bob's public key. An important element here, is that they have to find a way for Bob to send Alice her public key in a trusted way, so that Eve cannot intercept it, and change the keys. For this, we introduce Trent, and who is trusted by Bob and Alice to prove their keys. For this Trent signs the public key of Bob with his private key, and then Alice uses Trent's public key to prove Bob's public key.

For a few decades, RSA has been the main method in supporting public key encryption. We often use it when we connect to a secure Web site, and where the RSA method is used to prove the identity of the Web site. In this case the RSA public key of the site is presented to the user in the form of a digital certificate — and which is signed by a trusted source. The Web site can then prove its identity by signing a hash of the data with its private key, and the client can check this. A typical size of the public modulus is now 2,048 bits (created by two 1,024 bit prime numbers), and with some sites supporting 4,096 bits. So while desktop computers have the processing power to cope with these large numbers, less able devices (such as for low processing powered IoT — Internet of Things — devices) will often struggle to perform the necessary calculations.

So let's take a simple implementation of RSA key generation, encryption and decryption. In this case the code is:

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

In this case, we generate two random prime numbers ($p$ and $q$) for a given number of bits. The more bits we use, the more secure the method is likely to be, as an increase in the number of bits increases the number of prime numbers that can be searched for. Once we have these, we then determine the public modulus ($N$) by multiplying the prime numbers together. The difficulty of the problem is then factorizing this modulus back into the prime numbers. If we have the public modulus, it is fairly simple to then find the decryption exponent value. In most modern examples of RSA, we select a public exponent value ($e$) of 65,537, and so our encryption key becomes $(65,537,N)$. The decryption exponent ($d$) is then the inverse of $e \pmod {\phi}$ (and where $\phi=(p-1)(q-1)$).

A test run using 60-bit prime numbers is:

RSA has been around for over 46 years, and is still going strong. It can encrypt and it can sign. While the prime numbers involved has got larger, and it needs to have padding applied, it is still one of the best public key methods around, and well used on the Web.

Cybersecurity Cloud Lesson 1 rule book in key management for companies:

1. Your encryption keys are the keys to your castle. So protect them with your life!
2. Your enemy is you! The main threat is insiders, so beware of yourself and others in your company.
3. Beware of those that you trust and who you partner with. They can be your enemies, too.
4. For sensitive data, try not to let Amazon or Microsoft manage your keys.
5. Put your private keys in an HSM (Hardware Security Module). A shared HSM is fine, but if you have funds, create your own Cloud HSM.
6. If you are audited for your keys, you may need an on-premise HSM to link to your Cloud instance.
7. Create meaningful tags for your keys that make sense for everyone. Don't tag them as "Key1", "Key2", and so on. Give them meaning, "Main Active Directory Single Sign-on Key for Sales in Europe". Add words that allow you to search for keys easily.
8. Log the usage of your keys everywhere and link to people, roles, services and applications. Log, log and log some more.
9. Watch out for those keys being deleted … it is one of the easiest hacks for a disgruntled employee to perform.
10. Watch out for key wrapping from your insiders and your key exports. See Point 1.
11. Use a tiered alerting system which escalates the severity of the key usage, but make sure you keep those logs.
12. Use envelope encryption.
13. Test, test, and test some more.
14. Audit, audit, and audit. On a daily basis, if nescessary.
15. Test those encrypted backups.
16. We all make mistakes. If you delete a key, please say, as we have 60 days to undelete it.
17. Use key rotation wherever possible.
18. Just because ECDSA and EdDSA sound all fancy and brand new doesn't mean that RSA is not an option.
19. RSA is still your friend. Forget about those doom sayers on quantum cracking.
20. MD5 and SHA-1 should never, ever, be seen.
21. Beware of DevOpSec. They can be sloppy with their keys. Tell them off for doing risky things!

I had better stop here. So, finally, put a large poster on the wall that says, "no key, means no data!", "the enemy is within and around you!", "A breach of the trust infrastructure is one of the most expensive cybersecurity threats to resolve", "A single key breached, and this company could be finished!".

Sorry for being so coarse in places, but handling keys is a serious business.

Demos

These are:

• Quadratic residues: https://asecuritysite.com/primes/q_res
• Jacobi symbol: https://asecuritysite.com/primes/jac
• Jacobi and Legendre symbol: https://asecuritysite.com/primes/jacobi

Introduction

Remember at school that class where the teacher taught you about how to square something? It was great, and where we loved to take the square of 3 and get 9, and the square of 5 gave us 25. But, in the next lesson, we came back to earth with a bump, as it was time for the nasty little square root. Now, we have to find two numbers which when multiplied together, gave us 121, or 196. Luckily, there was a convenient button on the calculator that give us our quick answer. In the time before calculators, though, working out more complex square roots involved tables of logarithms. And, so, in this podcast, I will outline a difficult problem … find a square root in a modulo n world … aka quadratic residues.

In cryptography, we look for hard problems to solve. For this, we can create a backdoor into the problem and solve the problem. With discrete logarithms, we have a hard problem of:

Y=g^x (mod p)

and where it is difficult to determine x, even though we know g, Y and p, but as long as the prime number if large enough. Another hard problem is used in the RSA public key method, and this involves the difficulty in factorization at modulus (N) which is made up of two prime numbers.

Another hard problem is quadratic residues modulus n, and uses the form of:

x²=a (mod p)

and where we must find a value of x which results in a value of a (mod p). If a solution exists, the value of a is a quadratic residue (mod n).

In modular arithmetic, this operation is equivalent to a square root of a number (and where x is the modular square root of a modulo p). In the following, we will try and solve for the value of x, and also generate the Legendre symbol value.

For example, if we have a=969 and p=1223, we get:

Solve x²=968 (mod 1223) [Ans: 453] Try!

and:

Solve x²=1203 (mod 1223) [Ans: 375] Try!

Thus 968 and 1203 are quadratic residues modulo 1223.

The form of x²=a (mod p) is not always solvable. For example, if we have a=209 and p=1223 , we get:

x²=209 (mod 1223)

Also, if a shares a factor with p it is also not solvable. For example:

x²=39 (mod 13)

will return a zero value for x.

If we take a value of p=53, we get the following values [here]:

A sample run of the code gives:

In this case, we see that 10 is a possible quadratic residue for a p of 53. The solution is thus:

10²=47(mod 53)

You can see a demonstration here and here are some examples:

• Solve x²=12 (mod 13) [Ans: 8] Try!
• Solve x²=968 (mod 1223) [Ans: 453] Try!
• Solve x²=1203 (mod 1223) [Ans: 375] Try!
• Solve x²=47 (mod 53) [Ans: 10] Try!
• Solve x²=209 (mod 1223) [No solution!] Try!
• Solve x²=888 (mod 1223) [No solution!] Try!
• Solve x²=39 (mod 13) [No solution!] Try!

In science, it is difficult to avoid Adrien-Marie Legendre, as there are so many things named after him: Fourier–Legendre series; Gauss–Legendre algorithm; Legendre chi function; Legendre duplication formula; Legendre–Papoulis filter; Legendre form; Legendre polynomials; Legendre sieve; Legendre symbol; Legendre transformation; Legendre wavelet; Legendre–Clebsch condition; Legendre–Fenchel transformation; Legendre's constant; Legendrian knot; and Gamma function–Legendre formula.

And, so, where does Legedre help with your online security? Well, you will find his method used in elliptic curve methods, which are used to protect your online identity, and the security of the communications that you have with this Web page. So, let's look at the Legendre Symbol.

For this, we turn to Legendre who, in 1798, defined the Legendre symbol. In the following, we will try and solve for the value of x, and also generate the Legendre symbol value [link]:

Solve x²=12 (mod 13)

With his method, we can determine that the answer is 8, as 64 (mod 13) is 12. Some sample code is [here]:

A quadratic residue relates to the solving of the form: y=x² (mod n), and where we need to find values of y for different values of x and for a given modulus (n). For n=11, we get Z∗p={1, 3, 4, 5, 9}. This is because, 1² (mod11)=1, 2² (mod11)=4, 3² (mod11)=9, 4² (mod11)=5, 5² (mod11)=3, 6² (mod11)=3, 7² (mod11)=5, 8² (mod11)=9, 9² (mod11)=4, and 10² (mod11)=1.

To find the quadratic residues for a given modulus, we can use the Jacobi symbol is:

and is defined as:

The legendre_symbol returns:

• 1. When a is a quadratic residue of p.
• -1. When a is a quadratic nonresidue of p.
• 0. When a shares a factor of p.

The Jacobi symbol was defined by Carl Gustav Jacob Jacobi as a generalized form of the Legendre symbol.

While we have a trivial example here, we can use it for more complex ones, such as finding a point on the elliptic curve [here]. A sample run is:

The code for this is [here]: