如何确保某人没有使用公钥生成签名

Question

我遵循这些指示，https://www.onebigfluke.com/2013/11/public-key-crypto-math-explained.html。我的问题是--如果某个恶意代理没有写恶意消息，我如何知道，然后使用我的公钥生成一个签名？例如：

1. Bob有他的私钥。
2. Eve向爱丽斯发送一条消息，以及用鲍勃的公钥计算出来的“确认”。
3. Alice收到消息和Bob的公钥，计算确认==签名=>消息是由Bob (？)
4. 发送的，这与鲍勃发送消息和使用他的私钥计算的签名有什么不同？

G 210

编辑

privatekey = (95,49) # Bob's private key
publickey = (95,25) #Bob's public key
message = 122 #Eve writes a mallicious message
hash = message**65537 % 2**8 #Eve computes the hash
sig = hash**publickey[1]%publickey[0] #Eve computes the signature using bob's public key
Letter = (message, sig) #Eve sends her message and the signature to Alice
Alice_hash = Letter[0]**65537 % 2**8 #Alice computes the hash on her own
Alice_confirmation = Alice_hash**publickey[1]%publickey[0] #Alice computes the confirmation
if Alice_confirmation == Letter[1]:
    print("The message was sent by Bob")

它起作用了。我搞错了什么地方？(使用私钥计算的唯一方法是签名，但也可以使用公钥计算，除非我遵循的教程(上面的链接)是错误的)

Answer 1

这个问题一点也不傻。非对称密码学有点混乱。在这个话题上，我总是需要回忆一下，因为我每天都不使用它。

非对称密码学的核心是拥有公共密钥和私钥的概念。您可以使用其中之一将消息转换为密码，但您只能使用另一种方法将密码转换回消息。

因此，如果Alice想对Bob加密一条消息，她会应用Bob的公钥，甚至连Alice自己也无法解密该消息，因为她需要应用Bob的私钥，而只有Bob才能解密。使用两次公钥将不起作用。

这就像一个有两个钥匙的锁，一个用来锁，另一个用来解锁。

如果艾丽斯想要签个字，它的效果正好相反。她用她的私钥，只有她有。鲍勃，或者任何人只要能安全地证实她的公钥，就可以核实爱丽丝的身份。如果夏娃能让鲍勃相信公钥是爱丽丝的，而实际上是伊芙的钥匙，她用她的私钥签署了信息，那么这将是一次成功的攻击。

与加密示例一样，使用公钥进行签名并使用相同的公钥进行检查将不起作用，它必须是一个用于签名，另一个用于检查。这就是为什么它被称为不对称。

您描述的攻击失败了，因为Eve试图使用Bob的公钥签名一条消息。如果Alice再次使用Bob的公钥验证此消息，则验证将失败。

代码评审

在给出了代码示例和指向源代码的链接之后，我能够进一步了解它。

在我们开始之前:如果所有操作都是正确的，那么使用两次公钥将不会获得与先应用私钥，然后应用公钥相同的结果。这就是你建议的攻击失败的原因。让我们了解一下为什么攻击似乎在您的代码中起作用：

问题1:当您从示例中传输代码时，您的代码中有一个bug。这条线

hash = message**65537 % 2**8  # incorrect

应该用乘法代替幂函数。

hash = message*65537 % 2**8  # correct

这个bug在你身上，但从现在起没有什么是你的错，因为你所链接的源本身就是错误的。因此，让我们继续并一点一点地修复您的代码。

我将切换到用私钥签名和用公钥检查的常规情况，以确保算法有效，然后我们将再次运行您的攻击。

问题2: Alice_confirmation未正确计算。其思想是Bob计算哈希，然后加密哈希以获得签名。现在，Alice对签名进行解密，并将其与散列进行比较，而哈希也会进行计算。在示例中，最后一步被切换了。

所以这就是

Alice_confirmation = Alice_hash**publickey[1] % publickey[0]
if Alice_confirmation == sig:
    print("The message was sent by Bob")

实际上应该改为如下所示：

Alice_confirmation = sig**publickey[1] % publickey[0]
if Alice_confirmation == Alice_hash:
    print("The message was sent by Bob")

这是一个关键的区别，也是为什么你的攻击似乎奏效的原因。如果我没有弄错，副作用是正确签名的消息将无法通过测试(不过，由于问题1，这在您的原始代码中没有发生)。

问题3:我无法重建您如何获得私钥和公钥，所以我将使用示例网站提供的密钥。这里的问题是，作为一个规则，散列必须小于n。在您的例子中，哈希可以增长到255 (由于% 2**8)，这个值大于n= 91。这在网站上就更糟了，因为他们在哈希函数中使用了% 2**32，从而创造了更多的数字。

因此，让我们以https://en.wikipedia.org/wiki/RSA_(cryptosystem)维基百科页面提供的值为例。我们鼓励您尝试并滚动您自己的，只需确保它们足够大以满足您的哈希函数范围。

公钥:n= 3233，e= 17

私钥:n= 3233，d= 413

在这里，您的散列函数可以工作，因为应用% 2**8保证结果小于256，因此小于n= 3233。一般来说，使用更强的散列(如示例链接(message * 2654435761 mod 2**32)中提供的哈希)可能是个好主意，但当然，您必须适当地选择n，这样它就超过了2**32)。

因此，应用修复程序并稍微清理代码将使我们得到以下结果：

private_key = (3233, 17) # Bob's private key
public_key = (3233, 413) # Bob's public key

bob_message = 122

bob_hash = bob_message * 65537 % 2**8
bob_sig = bob_hash**private_key[1] % private_key[0]

# Alice receives Bob's message and his signature

alice_hash = bob_message * 65537 % 2**8  # same as bob_hash
alice_confirmation_hash = bob_sig**public_key[1] % public_key[0]

if alice_hash == alice_confirmation_hash:
    print("The message was sent by Bob")
else:
    print("The message was not sent by Bob")

print()
print(f"message: {bob_message}, signature: {bob_sig}")
print(f"hash: {alice_hash}, confirmation: {alice_confirmation_hash}")

如果运行此代码，将得到以下输出：

The message was sent by Bob

message: 122, signature: 1830
hash: 122, confirmation: 122

如果您想知道为什么消息与散列相同，这是您的消息小于2**8的结果。大于该值的消息将提供与消息不同的散列。

现在让我们运行您建议的攻击: Eve在计算签名时使用Bob的公钥。这将导致Alice在尝试验证签名时第二次使用公钥，结果如下：

The message was not sent by Bob

message: 122, signature: 1159
hash: 122, confirmation: 1891

因此，这里的哈希和确认哈希不匹配。伊芙的攻击失败了。