用 RSA 进行公平的网络抛硬币

/ 0评 / 0

这个思想事实上是我在小学三年级订阅的一本数学杂志上看到的。但是我现在已经完全忘记了具体的算法是什么了,只记得其包含大素数、取模(当时还不能叫取模,而必须写成除以几的余数)以及猜奇数还是偶数。之所以要这么做是为了不依赖于分歧终端机来解决一个问题(因为分歧终端机需要面对面才能保证公平性,当产生分歧的两方相隔太远时这是不现实的,而且引入第三方验证只会让事情变得更复杂)。

那么,其实就是一个非对称加密,一方提供一个公钥,要求对方猜出其私钥在 16 进制下反写的奇偶性。我们来模拟一个会话。

Alice: [Generates 512-bit RSA keypair.]
Alice: [Has public key:]
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAM4EQmJX05uWvMBryGddqI2CVEHLPThi
jhpYqvqWtSPwUfvvcyV+pJ1U8ItBpLs0mwn8ezPKpdmYvdvMuHoGdmkCAwEAAQ==

[Has private key:]
MIIBPAIBAAJBAM4EQmJX05uWvMBryGddqI2CVEHLPThijhpYqvqWtSPwUfvvcyV+
pJ1U8ItBpLs0mwn8ezPKpdmYvdvMuHoGdmkCAwEAAQJAKJUyNokyiB3DhOw2iBYt
E+Mukd9laewQLiR1WfPCLxfXe11Uq4P+ipb7TxPbOL64jC82WRdmnEIn2Ja/5J3I
uQIhAPZID2TTD899jTEqcvxL0mmXrvKZ7GTx/OoTD+y+gtp7AiEA1iVxZ/mA/sta
9uZbNELtQJQOvhhizOiLmsd04lnM32sCIQDhgQnXYArSCjwGEMBIk4SOev0N1jLG
G21hRyMFu0tFkQIhALbR9IV9nsDnv1r1wntVf9MYE5X6n66sATM8gO8VFzDNAiEA
hVuHby2MhizK7TgNF5KRW8YIH3JlX3/m+qfmZAEC1kM=

Alice: Public key in BASE64 is 

MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAM4EQmJX05uWvMBryGddqI2CVEHLPThi
jhpYqvqWtSPwUfvvcyV+pJ1U8ItBpLs0mwn8ezPKpdmYvdvMuHoGdmkCAwEAAQ==

Bob: Acknowledged.
Bob: [Encrypts string "deadbeef" with the public key provided.]
Bob: Send me the decrypted string of 

edJuXIgep5ZWuCCzn06qymM8j24Z96gKp09ehawQ529oXe1J6ovdxCcYqICN7Zqy1qJQPpNuDD3steoGJrl2rw==

Alice: [Decrypts string with private key.]
Alice: The decrypted string is 

deadbeef

Bob: Is it EVEN?

Alice: No. It is ODD. The private key in BASE64 is

MIIBPAIBAAJBAM4EQmJX05uWvMBryGddqI2CVEHLPThijhpYqvqWtSPwUfvvcyV+
pJ1U8ItBpLs0mwn8ezPKpdmYvdvMuHoGdmkCAwEAAQJAKJUyNokyiB3DhOw2iBYt
E+Mukd9laewQLiR1WfPCLxfXe11Uq4P+ipb7TxPbOL64jC82WRdmnEIn2Ja/5J3I
uQIhAPZID2TTD899jTEqcvxL0mmXrvKZ7GTx/OoTD+y+gtp7AiEA1iVxZ/mA/sta
9uZbNELtQJQOvhhizOiLmsd04lnM32sCIQDhgQnXYArSCjwGEMBIk4SOev0N1jLG
G21hRyMFu0tFkQIhALbR9IV9nsDnv1r1wntVf9MYE5X6n66sATM8gO8VFzDNAiEA
hVuHby2MhizK7TgNF5KRW8YIH3JlX3/m+qfmZAEC1kM=

The reverse of the private key is

346d2010466e7aaf6ef7...1020c3102803

Bob: Private key verified.

这里有一个好处就是双方都可以验证密钥的有效性。对于 Alice 而言,她可以用私钥解密 Bob 通过其公钥加密的消息,也可以用自己的私钥加密信息发送给 Bob 用公钥解密,从而确定私钥是和公钥配对且无法更改的。这就保证了整个抛硬币过程的公平。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注