Having a better understanding of modulus and the one-way function provides us the basis for our key exchange.\u00a0Think of this like Alice and Bob trying to create a secret handshake without ever meeting in person, while others are watching them. Here's how it works:<\/p>\r\n
The modular exponent power rule tells us [latex]\\left(g^{a} \\bmod p\\right)^{b} \\bmod p=\\left(g^{b} \\bmod p\\right)^{a} \\bmod p[\/latex]. This means they both end up with the same secret number, even though they never shared their secret numbers with each other!\u00a0\u00a0<\/p>\r\n
Let's see this with real numbers.<\/p>\r\n [latex]\\begin{array}{llll} & \\textbf{Alice} & & \\textbf{Bob} \\\\ \\text{Alice and Bob publically} & g=3, p=17 & \\text{Common info} & g=3, p=17 \\\\ \\text{share a generator and prime} & & & \\\\ \\text{modulus.} & & & \\\\ \\text{Each then secretly picks a} & n = 8 & \\text{secret number} & n=6 \\\\ \\text{number n of their own.} & & & \\\\ \\text{Each calculates } g^n \\bmod p & 3^{8} \\bmod 17=16 & & 3^{6} \\bmod 17=15 \\\\ \\text{They then exchange these} & A=16 & & B=15 \\\\ \\text{resulting values.} & B=15 & & A=16\\\\ \\text{Each then raises the value} & B^{n} \\bmod p= & \\text{mix in secret} & A^{n} \\bmod p=\\\\ \\text{they received to the power of } & & \\text{number} & \\\\ \\text{their secret }n \\bmod p & 15^{8} \\bmod 17=1 & & 16^{6} \\bmod 17=1\\\\ \\text{The result is the shared secret key.} & 1 & \\text{shared secret key} & 1 \\end{array}[\/latex]<\/p>\r\n The shared secrets come out the same because of the modular exponent power rule:<\/p>\r\n [latex]\\left(a^{b} \\bmod n\\right)^{c} \\bmod n=\\left(a^{c} \\bmod n\\right)^{b} \\bmod n[\/latex].<\/p>\r\n Alice computed [latex]\\left(3^{6} \\bmod 17\\right)^{8} \\bmod 17[\/latex] while Bob computed [latex]\\left(3^{8} \\bmod 17\\right)^{6} \\bmod 17[\/latex], which the rule says will give the same results. Notice that even if a snooper were to obtain both exchanged values [latex]A = 16[\/latex] and [latex]B = 15[\/latex], there is no way they could obtain the shared secret key from these without having at least one of Alice or Bob\u2019s secret numbers. There is no easy way to obtain the secret numbers from the shared values, since the function was a one-way function.<\/p>\r\n\r\n[\/hidden-answer]<\/section>\r\n RSA is one of the most widely used methods in modern cryptography. It uses a public-private key system where anyone can encrypt a message using your public key, but only you can decrypt it with your private key. This is similar to having a special lock where copies of the public key can be freely distributed - anyone can use it to secure a message, but only the holder of the private key can unlock and read those messages.<\/p>\r\n The security of RSA relies on a fundamental principle in mathematics: the difficulty of factoring large numbers into their prime components. For example, while it's straightforward to multiply [latex]53[\/latex] times [latex]59[\/latex] to get [latex]3127[\/latex], finding the original prime factors of [latex]12,317[\/latex] is considerably more challenging. This difficulty increases exponentially when working with prime numbers that are hundreds of digits long, making it computationally infeasible to break the encryption.<\/p>\r\n Here's how RSA encryption works:<\/p>\r\n The strength of RSA lies in its mathematical foundation: even with knowledge of the encrypted message and public key, determining the original message is computationally infeasible without access to the private key. This makes RSA a cornerstone of modern secure communications.<\/p>\r\n Suppose Alice has generated these values for her RSA system:<\/p>\r\n How would Bob send Alice the secret message [latex]50[\/latex].<\/p>\r\n <\/p>\r\n You can view the transcript for \u201cPrime Numbers & RSA Encryption Algorithm - Computerphile\u201d here (opens in new window).<\/a><\/p>\r\n You can view the transcript for \u201cHow RSA Encryption Works\u201d here (opens in new window).<\/a><\/p>\r\n
\r\n[reveal-answer q=\"4330\"]Show Solution[\/reveal-answer]
\r\n[hidden-answer a=\"4330\"]
\r\nRSA<\/h2>\r\n
\r\n\t
\r\n\t
\r\n\t
\r\n\t
\r\n\t
\r\n[reveal-answer q=\"4331\"]Show Solution[\/reveal-answer]
\r\n[hidden-answer a=\"4331\"]
\r\nBob starts with his message [latex]50[\/latex] and has access to Alice's public key information: [latex]n = 3127[\/latex] and [latex]e = 3[\/latex].\u00a0
\r\n[latex]\\\\[\/latex]
\r\nTo encrypt his message, he computes:
\r\n
\r\n
\r\nWhen Alice receives the encrypted message [latex]3047[\/latex], she can use her private key [latex]d = 2011[\/latex] to decrypt it by calculating:
\r\n
\r\nThis gives her back Bob's original message of [latex]50[\/latex].
\r\n[latex]\\\\[\/latex]
\r\nNote: Only Alice, who has the private key [latex]d[\/latex], can perform this decryption. Anyone intercepting the encrypted message [latex]3047[\/latex] would not be able to determine that the original message was [latex]50[\/latex].
\r\n[\/hidden-answer]<\/section>\r\n
\r\n[videooption displayName=\"Prime Numbers & RSA Encryption Algorithm - Computerphile\" value=\"https:\/\/youtu.be\/JD72Ry60eP4\"][videooption displayName=\"How RSA Encryption Works\" value=\"\/\/plugin.3playmedia.com\/show?mf=12427540&p3sdk_version=1.10.1&p=20361&pt=375&video_id=ZPXVSJnDA_A&video_target=tpm-plugin-0nwtzzf9-ZPXVSJnDA_A\"] [videooption displayName=\"RSA Encryption Algorithm - Rivest\u2013Shamir\u2013Adleman - RSA Algorithm Explained - Simplilearn\" value=\"\/\/plugin.3playmedia.com\/show?mf=12427541&p3sdk_version=1.10.1&p=20361&pt=375&video_id=vf1z7GlG6Qo&video_target=tpm-plugin-le13zkx0-vf1z7GlG6Qo\"]
\r\n[\/videopicker]\r\n\r\n