YOUR ULTIMATE RESOURCE ON THE NEW
DIGITAL ECONOMY
Topics about Smart Cities, Fintech, Digital Marketing, Internet of Things, Social Media and Everything Else
by Yap Heng Kiong
This post discusses the Public/Private Key encryption and cryptography technique used in Bitcoin and Blockchain. Follow my other articles to find out more about Blockchain and how it works.
Issues with Symmetric Key System
This is how the One-key (or symmetric) encryption system works. A Sender encrypts the message to be sent using a private key. The private key is then used by the Receiver to decrypt in order to receive the message. The risk of such a system is that anyone else could potentially obtain the private key and able to receive the message though not authorised.
Symmetric key algorithms are algorithms for cryptography that use the same key for both encryption and decryption.
Plaintext is the unencrypted message whereas Ciphertext is the encrypted message. The issues are:
Encryption Used in Blockchains - Asymmetric Key Algorithms
Blockchain and bitcoin use Asymmetric key algorithms to protect transaction messages across the network.
James Henry Ellis (25 September 1924 – 25 November 1997) was a British engineer and cryptographer. In 1970, while working at the Government Communications Headquarters (GCHQ) in Cheltenham he conceived of the possibility of "non-secret encryption", more commonly termed public-key cryptography. (Wikipedia https://en.wikipedia.org/wiki/James_H._Ellis)
Instead of sharing a private key, A makes available publicly the lock (public key) which only his private key can be used to open. A then sends the lock to B. B uses the lock to secure and send the message to A. Since the key is private to A, the encrypted message (locked message) will not be subjected to any eavesdropping, e.g. E. Blockchain and bitcoin encrypt transaction messages makes use of public-key cryptography. How Public/Private Cryptography works?
Clifford Christopher Cocks CB FRS is a British mathematician and cryptographer. Cocks, with his background in number-theory, developed the idea of using prime factorisation to implement Public/Private Key Cryptography, which later became known as the RSA encryption algorithm.
What is prime factorisation? In number theory, the fundamental theorem of arithmetic, also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer greater than 1 either is prime itself or is the product of prime numbers. (Wikipedia - https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic). For example, 30 = 5 X 3 X 2 589 = 31 X 19 437231 = 859 X 509 The Euler totient function ϕ Based on another theory proposed by Leonhard Euler in 1760, we introduce Euler phi function, written ϕ(n), ϕ(n) is the number of non-negative integers less than n that are relatively prime to n. In other words, if n>1 then ϕ(n) is the number of elements in Un, and ϕ(1)=1. Hence, ϕ(6) = 2 [1,2,3,4,5,6] ϕ(7) = 6 [1,2,3,4,5,6,7] - 7 is a Prime number ϕ(8) = 4 [1,2,3,4,5,6,7,8] ϕ(13) = 12 [1,2,3,4,5,6,7,8,9,10,11,12,13] - 13 is a Prime number There is an interesting pattern we can observe from the Euler totient theory above, i.e. ϕ(n) = n-1 (if n is a prime number).
Blockchain uses the RSA algorithm to send and sign an encrypted message without a separate exchange of a symmetric key,
To see the implementation of Public/Private Key in action, STEP 1 choose two distinct primes P=11 Q=7 STEP 2 Find N; where N is the product of P and Q. N=PXQ=11X7=77 STEP 3 From above Euler totient theory, we know that ϕ(N)=N-1 and since ϕ(PXQ)=(P-1)X(Q-1); we can determine ϕ(N) In number theory, Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. ... Euler's totient function is a multiplicative function, meaning that if two numbers m and n are relatively prime, then φ(mn) = φ(m)φ(n). (Wikipedia - https://en.wikipedia.org/wiki/Euler%27s_totient_function)
Therefore
ϕ(N)=ϕ(77)=(P-1)X(Q-1)=(11-1)X(7-1)=10X6=60 (Since P & Q are prime numbers) STEP 4 Next, we choose an Encryption Key (e) or the lock(also known as the public key) as illustrated above. e should be a prime number greater than 1 but less than ϕ(N), and the greatest common divisor, gcd(e, ϕ(N) ) = 1 this means e should be coprime to φ(N). In number theory, two integers a and b are said to be relatively prime, mutually prime, or coprime (also written co-prime) if the only positive integer (factor) that divides both of them is 1. ... This is equivalent to their greatest common divisor being 1. (Wikipedia - https://en.wikipedia.org/wiki/Coprime_integers)
The following numbers satisfy the condition 1 < e < ϕ(N) or 1 < e < 60, where e is a prime number.
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59. In this case, let's choose 37 as e. Click on link below to use a tool to find out if gcd(e,ϕ(N)) or gcd(37,60)=1
Alternative, here's how to determine gcd
60 = 2 x 2 x 3 x 5 i.e. GCF(37,60) = 1 since there are no common prime factors. In another example 4 = 2 x 2 40 = 2 X 2 X 2 X 5 i.e. GCF(4,40) = 4 (2X2) Therefore the Encryption key (or the lock) is (37, 60). A hides P, Q and ϕ(N); and sends only (e, N) or (37, 60) to B. B has a message to send to A. B uses the Encryption key (or public key) to protect the message (Plaintext) to send to A. A uses a private key (Decryption key) to decrypt the Ciphertext back to Plaintext. The next step shows how the Decryption key is being derived. The Decryption key (d) is derived from and hence is related to the Encryption key (e)
STEP 5
Next, determine d, the Decryption key from the Encryption key (e), which is private to A. (Source - https://www.youtube.com/watch?v=fz1vxq5ts5I)
Since d X e ≅ 1 (mod N)
d X 37 ≅ 1 (mod 60) d ≅ 37^-1 (mod 60) 37^-1 (mod 60) = ??
First write down
LHS=60 and RHS=37; Determine the remainder to make LHS=RHS. Hence, 60 = 37 X 1 + 23 Bring 37 and 23 to the left; and repeat the same process above, until you get remainder =1 as shown below.
Once completed, move the numbers around for each line, until you get the following on the right.
Remember we started with:
d ≅ 37^1 (mod 60) 37^1 (mod 60) = ?? Therefore d = 8X60/37=13 Therefore the Encryption key (or the lock) is (37, 60). the Decryption key (or the private key) is (13, 60). Encryption and Decryption of the Message
Step 6
To summarise, we have the following: P=11 Q=7 N=11X7=77 ϕ(N)=ϕ(77)=60 e=37 d=13 Assume that B has a message to send to A. The Message, M=15 A sends B the lock (Encryption key): e=37, N=77; B performs the encryption using the following: M^e MOD N = C How MOD works?
Step 7
A receives C=71 from B. A performs the decryption using the following: C^e MOD N and get M=15
In actual Blockchain and Bitcoin implementation, P and Q are chosen to be very large numbers.
Resources
https://www.youtube.com/watch?v=O-4_oS3G7MI&t=271s&list=PLoNXVEI2Gdc8CnLo4ceaArsXVoLwWcbj0&index=3
1 Comment
2/27/2024 11:04:08 pm
IoT (Internet of Things) SIM cards are specialized subscriber identity modules designed for connecting IoT devices to cellular networks. These SIM cards enable machines, sensors, and other IoT devices to transmit data over cellular networks, facilitating communication and remote monitoring. They are often tailored to the specific needs of IoT applications, offering features like low power consumption, security protocols, and flexible data plans. IoT SIM cards play a crucial role in the proliferation and functionality of IoT deployments across various industries.
Reply
Leave a Reply. |