# Happy Birthday to John Napier … Helping To Build A More Trusted World

Last week (4 April) wasthe birthday of John Napier, and who is one of Edinburgh’s (and the world’s) greatest scientists. I am so proud to work in the same tower that John Napier accompanied all those years ago. He may be forgotten by many and disliked by pupils but he is one of the true geniuses that changed our world.

And so, we are now building a new world build on cryptography, and with methods build on the factorization of prime numbers struggling to cope with the advance of technology, it is to discrete logarithms that we increasingly look too for our new inspirations.

For new ways of building trust, it is discrete logarithms that provide us with a way to protect privacy. In the following, I have created a program which allows voters to hide their voting

`import randomimport mathimport sysg=2p=67nvoters = 5voter = [int] * nvoterspublic = [int] * nvotersY = [int] * nvotersmake_votes = [int] * nvotersvote = [int] * nvotersvote[0]=0vote[1]=0vote[2]=0vote[3]=0vote[4]=0def extended_euclidean_algorithm(a, b):"""    Returns a three-tuple (gcd, x, y) such that    a * x + b * y == gcd, where gcd is the greatest    common divisor of a and b.    This function implements the extended Euclidean    algorithm and runs in O(log b) in the worst case.    """    s, old_s = 0, 1    t, old_t = 1, 0    r, old_r = b, a    while r != 0:        quotient = old_r // r        old_r, r = r, old_r - quotient * r        old_s, s = s, old_s - quotient * s        old_t, t = t, old_t - quotient * t    return old_r, old_s, old_tdef inverse_of(n, p):"""    Returns the multiplicative inverse of    n modulo p.    This function returns an integer m such that    (n * m) % p == 1.    """    gcd, x, y = extended_euclidean_algorithm(n, p)    assert (n * x + p * y) % p == gcd    if gcd != 1:        # Either n is 0, or p is not a prime number.raise ValueError('{} has no multiplicative inverse ''modulo {}'.format(n, p))    else:        return x % pprint "Votes: ",vote[0],vote[1],vote[2],vote[3],vote[4]print "----"for i in range(0,nvoters):	voter[i] = random.randint(1, 30) for i in range(0,nvoters):	public[i] = g**voter[i]  % pfor i in range(0,nvoters):	Y[i]=1	for j in range(0,i): 		Y[i] = (Y[i] * public[j]) % p	for j in range(i+1,nvoters):		Y[i] = Y[i] * inverse_of(public[j],p) % pfor i in range(0,nvoters):	print "Public value: ",public[i]for i in range(0,nvoters):	print "Y value: ",Y[i]for i in range(0,nvoters):	make_votes[i] = (Y[i]**voter[i])*(g**vote[i]) % presult = make_votes[0]for i in range(1,nvoters):	result = (result *make_votes[i]) % pfor i in range(0,nvoters):	print "Vote ",make_votes[i] print "---"print "Vote tally: ",math.log(result)/math.log(g)`

We see the continual usage of the operation G (a generator) to the power of x:

Y = G^x

In a coding form this looks like:

`Y = G**x`

John would we this as a log base of G, and would immediately say that to find x we would have to take the inverse log to the base G of x. For example:

Y = 6³ = 6 x 6 x6 = 216

To take the inverse log we would get:

invlog[6](216) = log10(216)/log10(6) = 6

But we are not protecting any values here, so how do we protect the values. we bring in a prime number and use the mod operator:

Y = G^x mod P

now it is difficult (if G^x is much larger than P) to actually find the value of x that will give us a given Y value. Note that only certain values of G and P can be used together.

Bob, Alice and Trent can agree on G and P, and then Trent can calculate their total salary if Bob cases and encrypted value of:

Bob Salary (Encrypted) = G^{Bob salary} mod P

and Alice does the same:

Alice Salary (Encrypted) = G^{Alice salary} mod P

Trent then takes the encrypted values and multiplies them today, and returns the result, and which should be:

G^{Bob salary} x G^{Alice salary} = G^{Bob salary + Alice salary}

More details on how the method works here.

# Homomorphic encryption

It is now thanks to John Napier that we can now look to build privacy into everything that we do. One challenge is to make sure that we can operate on encrypted values. In we can perform mathematical operations on data without actually revealing the data.

With homomorphic encryption, defined by Craig Gentry in 2010 [here], we can operate on data without ever decrypting it. Craig defined a scenario where Alice had a jewellery box, which she locked with her key, and where her workers could not gain access to the gems contained with it. Then when they wanted to work on the gems, they could do so with special gloves but couldn’t remove them from the box.

With homomorphic encryption allows ciphered values to be moved to wherever they are required, and then processed, without giving away the original data. Data could thus traverse across the Internet and move to places that it is required, and then used to calculate results.

For your tax return we might see:

`Sales (Web)    &*X43=%Sales (Print) *65tfd1=              ----------Total Sales   64,532 (=B1+B2)`

In the sales values are ciphered, but we can still process the addition of the two values. We could also apply subtraction, multiplication and division.

We can achieve partial homomorphic encryption with the RSA method:

where we have V1 and V2 as values, an e is the encryption key. So when we decrypt, we will get the value of V1 multiplied by V2. For we pick a public key and a private one. Let’s take versions:

`public n: 130784737441990876177357958243693644830726563721360660466﻿5770676951886355197246857671425655271383319262162735337210458386204﻿0163830698132957651336978954339749368441676984294775404141089096283﻿2351079743260650676667850963174834563099364787739637456417087216464﻿138309745263545890374086809359145644559146264924083private lambda: 653923687209954380886789791218468224153632818606803﻿3023328853384759431775986234288357128276356916596310813676686052291﻿9310200819153490664788256684894771687304547314630213923451602062915﻿4472442118777485906270040640743230185779181324696482484077330728806﻿14461484567777528120031610918117114758246385659532477104Elapsed time (keygen): 364 ms`

Now go and try:

http://asecuritysite.com/encryption/pal

In next few years, expect to see a massive increase secure processing and in the passing of encrypted data. If you want to see how we can use a public and private key with homomorphic encryption, try here:

https://asecuritysite.com/encryption/hom_public

--

--

## More from ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

## Prof Bill Buchanan OBE

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. Based in Edinburgh. Old World Breaker. New World Creator. Building trust.