212
12 Cryptocurrencies
her secret a, but does not know Bob’s secret b. Beforehand, they publicly agree on
using two large numbers g and p, where p is a prime number and g is a primitive
root of p, which means that g
j
(mod p) for j = 1, . . . , p cycles through all integer
values between 1 to p − 1. Here a (mod p) denotes the remainder of an integer division of a by p. Once these preliminaries are established, Alice sends the number
A = g
a
(mod p) to Bob and Bob sends B = g
b
(mod p) to Alice, who calculates the
secret key via k = B
a
(mod p) = g
ab
(mod p). Bob arrives at the same key by calculating k = A
b
(mod p) = g
ba
(mod p). All further communication between them
can then use k as the key for encrypting and decrypting using one of the algorithms
mentioned before. Note that they arrive at the same secret key k without divulging
their private secrets to anyone. Moreover, an eavesdropper on the communication
channel—Eve—can only pick up g, p, A, and B, but faces the problem to determine
Alice’s secret a from knowing A = g
a
(mod p), which entails testing a large number
of trials for a in order to find one that produces A. If the numbers g and p are very
large, this is computationally not feasible. Despite the big advantage to agree on a key
k, the communication only works between two partners, here Alice and Bob, who
have to schedule a common session, when they work out k, before being able to use
it to encrypt their further communication. This complexity precludes spontaneously
sending of, for example, emails.
This deficiency was overcome in 1977 by the RSA public-key cryptographic system, developed by Rivest, Shamir, and Adelman. The algorithm is based on finding
positive integer numbers n, e, and d, such that for any message, witten as a positive
integer m with 0 ≤ m < n, we have m
ed
(mod n) = m. Here n and e constitute the
public key and d is the private key. Let us consider a standard scenario, where Alice
publishes her public key (n, e) on her web site and keeps the private key d to herself.
If Bob wants to send a message m to Alice, he looks up her public key (n, e) and calculates the encrypted message c = m
e
(mod n), which he sends to Alice over an open
communication channel. For different messages m the cipher text c jumps around
between 0 and n in a quasi-random fashion, which guarantees that it is practically
impossible to guess m from c, unless one has access to the private key d. Such functions, which are easy to calculate one way, but extremely difficult to invert, unless one
has access to the private key, are called trapdoor functions. Since Alice knows her
private key d, all she has to do is to calculate c
d
(mod n) = m
ed
(mod n) = m in order
to recover the plaintext message m. Eve, who desperately tries to know what Bob is
sending to Alice, has access to c, n and e but she has to try out all possible messages
¯
m that will actually produce the ciphertext c = ¯
m
e
(mod n). If n and e are large, this
is not feasible in a reasonable amount of time. We point out that this public-key
cryptographic system is the enabling technology that makes trading over the internet
possible. There would be no amazon.com or ebay.com without public-key cryptography. Whenever you see a https prefix of an internet address, public-key cryptography
is involved to exchange a symmetric key that allows faster communication and is
henceforth used to encrypt further communication, for example, to transmit credit
card details.
Secretly sending a message from Bob to Alice is only one possible application.
Imagine a scenario, where Eve is known to fake Alice’s signature in emails, so Alice
12 Cryptocurrencies
her secret a, but does not know Bob’s secret b. Beforehand, they publicly agree on
using two large numbers g and p, where p is a prime number and g is a primitive
root of p, which means that g
j
(mod p) for j = 1, . . . , p cycles through all integer
values between 1 to p − 1. Here a (mod p) denotes the remainder of an integer division of a by p. Once these preliminaries are established, Alice sends the number
A = g
a
(mod p) to Bob and Bob sends B = g
b
(mod p) to Alice, who calculates the
secret key via k = B
a
(mod p) = g
ab
(mod p). Bob arrives at the same key by calculating k = A
b
(mod p) = g
ba
(mod p). All further communication between them
can then use k as the key for encrypting and decrypting using one of the algorithms
mentioned before. Note that they arrive at the same secret key k without divulging
their private secrets to anyone. Moreover, an eavesdropper on the communication
channel—Eve—can only pick up g, p, A, and B, but faces the problem to determine
Alice’s secret a from knowing A = g
a
(mod p), which entails testing a large number
of trials for a in order to find one that produces A. If the numbers g and p are very
large, this is computationally not feasible. Despite the big advantage to agree on a key
k, the communication only works between two partners, here Alice and Bob, who
have to schedule a common session, when they work out k, before being able to use
it to encrypt their further communication. This complexity precludes spontaneously
sending of, for example, emails.
This deficiency was overcome in 1977 by the RSA public-key cryptographic system, developed by Rivest, Shamir, and Adelman. The algorithm is based on finding
positive integer numbers n, e, and d, such that for any message, witten as a positive
integer m with 0 ≤ m < n, we have m
ed
(mod n) = m. Here n and e constitute the
public key and d is the private key. Let us consider a standard scenario, where Alice
publishes her public key (n, e) on her web site and keeps the private key d to herself.
If Bob wants to send a message m to Alice, he looks up her public key (n, e) and calculates the encrypted message c = m
e
(mod n), which he sends to Alice over an open
communication channel. For different messages m the cipher text c jumps around
between 0 and n in a quasi-random fashion, which guarantees that it is practically
impossible to guess m from c, unless one has access to the private key d. Such functions, which are easy to calculate one way, but extremely difficult to invert, unless one
has access to the private key, are called trapdoor functions. Since Alice knows her
private key d, all she has to do is to calculate c
d
(mod n) = m
ed
(mod n) = m in order
to recover the plaintext message m. Eve, who desperately tries to know what Bob is
sending to Alice, has access to c, n and e but she has to try out all possible messages
¯
m that will actually produce the ciphertext c = ¯
m
e
(mod n). If n and e are large, this
is not feasible in a reasonable amount of time. We point out that this public-key
cryptographic system is the enabling technology that makes trading over the internet
possible. There would be no amazon.com or ebay.com without public-key cryptography. Whenever you see a https prefix of an internet address, public-key cryptography
is involved to exchange a symmetric key that allows faster communication and is
henceforth used to encrypt further communication, for example, to transmit credit
card details.
Secretly sending a message from Bob to Alice is only one possible application.
Imagine a scenario, where Eve is known to fake Alice’s signature in emails, so Alice