Simplest explanation of the math behind Public Key Cryptography (2013)

栏目: IT技术 · 发布时间: 4年前

内容简介:I was trying to explain1. Pick two prime numbers:2. Multiply them together:

I was trying to explain public key cryptography today and totally failed at it. Here are notes to myself based on various Wikipedia pages. There's a lot more to it than this (like padding ) but this is the gist of it.

1. Pick two prime numbers:

p = 7
q = 13

2. Multiply them together:

n = p * q
n = 7 * 13
n = 91

3. Compute Euler's " totient " function of n :

φ(n) = (p - 1) * (q - 1)
φ(91) = (7 - 1) * (13 - 1)
φ(91) = 6 * 12
φ(91) = 72

4. Pick a random number e such that:

1 < e < φ(n)
1 < e < φ(91)
1 < e < 72

and e is " coprime " with φ(n), meaning it has no common factors.

e = 23  (because I said so)

5. Compute d , the modular multiplicative inverse of e (mod φ(n)):

e^-1 = d (mod φ(n))
23^-1 = d (mod φ(91))
23^-1 = d (mod 72)
23 * d = 1 (mod 72)
23 * 47 = 1 (mod 72)
d = 47

Now you have all the magic numbers you need:

public key  = (n = 91, e = 23)
private key = (n = 91, d = 47)

Secret messages to you

1. Have someone else encrypt a message m using your public key (n, e):

m = 60
c(m) = m^e mod n
c(60) = 60^23 mod 91
c(60) = 44
c = 44  (they send this to you)

2. Decrypt the message c using your private key (n, d):

c = 44
m(c) = c^d mod n
m(44) = 44^47 mod 91
m(44) = 60
m = 60  (now you have the secret)

Prove you wrote something

1. Hash the message to broadcast (this is Knuth's insecure hash function):

broadcast = 102
hash(broadcast) = broadcast * K mod 2^32
hash(102) = 102 * 2654435761 mod 2^32
hash(102) = 169507974

2. Compute the signature with your private key (n, d):

signature = hash(broadcast) ^ d mod n
signature = hash(102) ^ 47 mod 91
signature = 169507974 ^ 47 mod 91
signature = 90

3. People who receive the broadcast message (102) and the signature (90) can confirm with your public key (n, e):

broadcast = 102
hash(broadcast) = broadcast * K mod 2^32
hash(102) = 102 * 2654435761 mod 2^32
hash(102) = 169507974
confirmation = hash(broadcast)^e mod n
confirmation = 169507974^23 mod 91
confirmation = 90  (matches your signature)

Why is this safe?

In this simple example it's totally not. You can trivially take n = 91 and guess p and q with simple factorization :

>>> set((91 / i) for i in xrange(1, 91) if 91 % i == 0)
set([91, 13, 7])

Redo all the math above and you have the private key. Doh~

Now imagine if n was such a large number that it took a very long time to guess p and q :

>>> set((12031294782491844L / i) for i in xrange(1, 12031294782491844L) if 12031294782491844L % i == 0)

This takes a really long time. Even fancy solutions on the fastest computer on Earth would take until the end of the universe. That's why transmitting secrets with public key cryptography is safe. That's also why great leaps in prime number theory are frightening / exciting.


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

无懈可击的Web设计

无懈可击的Web设计

西德霍姆 / 刘建宁 / 清华大学出版社 / 2009-4 / 59.90元

一个网站,无论视觉上多么美观,内容多么丰富,如果不能面向最广泛的用户群,那它就不算是真正成功的网站。《无懈可击的Web设计:利用XHTML和CSS提高网站的灵活性与适应性》是Web标准设计领域的公认专家Dan Cederholm的倾力之作,向您描述了基于Web标准的设计策略,以适应各种各样的用户浏览方式。书中每一章的开头都给出了一个基于传统HTML技术的实例,然后对它进行重构,指出它的局限性,并利......一起来看看 《无懈可击的Web设计》 这本书的介绍吧!

MD5 加密
MD5 加密

MD5 加密工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具