椭圆曲线迪菲-赫尔曼加密

• 下载源文件 - 45.4 KB

引言

椭圆曲线加密是当前公钥加密的标准，并被国家安全局推广为保障双方私密通信的最佳方式。在利用椭圆曲线加密算法方面，微软有好消息也有坏消息。好消息是，Vista 操作系统通过 CNG（下一代加密 API）原生支持它。坏消息是，要使用 EC 的托管库，要等到 Visual Studio Orcas 发布，而 Orcas 目前计划于 2007 年底或 2008 年初发布。

附件项目中的代码试图弥补这一不足，提供了一个包装类，该类可以访问底层的 Vista 加密 API，并提供利用椭圆曲线算法的简单方法。然而，它仅用于教育目的，在任何严肃的应用中都还需要大量的测试和重构。换句话说，请随意玩弄、复制和以任何您喜欢的方式修改它，但在当前形式下，请不要用它来举起任何重物。

背景

Vista 的 CNG 提供了用于椭圆曲线数学的工具，用于加密和数字签名。本项目仅处理前者，将 EC 与迪菲-赫尔曼协议（ECDH）结合使用。然而，底层的 P/Invoke 签名应该是一个很好的起点，适合任何想尝试解开 Vista 加密 API 的 ECDSA 功能的人。

非对称算法涉及使用公钥和私钥来隐藏数据。理论上，生成公钥和私钥后，用户将公钥发送给同事，同事使用公钥加密数据，然后将数据发回给原始用户。原始用户然后用他的私钥解密数据。私钥不应该可以从公钥推导出来（或者至少需要很长时间才能做到）。

在更常见的情况下，公钥和私钥用于加密和解密第三个密钥，该密钥用于对称加密和解密。之所以这样做，是因为与对称加密算法不同，公钥/私钥算法相对较慢，更适合加密少量数据。

迪菲-赫尔曼使用共享密钥来完成类似的事情。通信双方发送一个可以看到的公钥给对方。然后，公钥与私钥结合起来创建一个共享密钥，由于底层的数学原理，该密钥在双方都是相同的。然后，该共享密钥用于哈希一个新的密钥，双方都可以使用该密钥来加密和解密消息。

乍一看，这似乎有点奇怪（至少对我来说是这样）。Alice 生成密钥 A 和 B，并将 B 发送给 Bob。Bob 生成密钥 C 和 D，并将 D 发送给 Alice。不知何故，Alice 能够基于 A 和 D 生成第三个密钥（一个与她自己的密钥无关的密钥），并且生成 Bob 使用 C 和 B（他从未见过）生成的相同数字。

我发现解释这是如何可能的最好的文章之一是由 Keith Palmgren 撰写的，可以在此处找到。然而，在不理解详细数学的情况下，可以使用乘法给出一个简单的例子。想象一下，在通信的双方，我们已经就一个共同的种子数字达成一致，比如 2。Alice 发送给 Bob 的公钥可以是我们的种子和私钥的乘积。如果私钥是 10，那么 Alice 将发送给 Bob 的公钥是 20。如果 Bob 的私钥是 12，那么他将发送给 Alice 的公钥是 24。通过将 Bob 的公钥与她自己的私钥相乘，Alice 得到一个共享的密钥协议 240。在他的那一侧，Bob 将 12 和 20 相乘，得出相同的共享密钥。然后，这些乘积可以用来生成一个对称密钥，用于来回加密和解密消息。

由于数字很小，任何截获来回公钥的人都可以通过简单地找到其因子来轻松推导出两个私钥。然而，对于非常大的素数，以及涉及模运算而非乘法的生成例程，这项任务会变得越来越困难。

公钥加密算法的目标是使得从往来的公钥与我们自己保留的私钥之间很难找到任何联系。随着数学的进步，各种突破被发现，揭示了生成此类素数的新方法。椭圆曲线数学是这方面的最新进展，人们普遍认为它包含比我们过去十年使用的许多算法更难解决的问题集，因此能够生成公钥和私钥的算法也更强大。由于破解难度更大，因此将 EC 与迪菲-赫尔曼相结合被认为可以提高公钥加密的安全性。

需要指出的是，迪菲-赫尔曼以 Whitfield Diffie 和 Martin Hellman 的名字命名，他们两人在 70 年代首次提出了该协议。Ralph Merkle 也经常与他们的工作相关联，因为他在阐述公钥加密的用法方面做出了额外的贡献。

使用代码

使用我编写的 ECDiffieHellmanMerkle 包装器来访问 CNG API 非常简单。以下代码模拟了一个常见场景。两个用户 A 和 B 创建他们的 ECDiffieHellmanMerkle 实例，并传递一个表示 ECDH 强度的枚举值。他们将各自的公钥发送给对方，对方使用它来生成密钥。下面的代码执行最终测试，以证明密钥是相同的。然后，该密钥可用于双方之间的消息加密和解密。如果无法访问任何一个私钥，则第三方将很难推导出共享密钥。

ECDiffieHellmanMerkle A = new ECDiffieHellmanMerkle(ECDHAlgorithm.ECDH_256);
ECDiffieHellmanMerkle B = new ECDiffieHellmanMerkle(ECDHAlgorithm.ECDH_256);
byte[] SecretA = A.RetrieveSecretKey(B.PublicKey);
byte[] SecretB = B.RetrieveSecretKey(A.PublicKey);
string strSecretA = Encoding.ASCII.GetString(SecretA);
string strSecretB = Encoding.ASCII.GetString(SecretB);
MessageBox.Show((strSecretA.Equals(strSecretB)).ToString());

默认情况下，ECDH 使用 SHA1 哈希密钥，该哈希密钥仅生成 160 位密钥。如果我们想使用符合 AES 标准的算法，例如 .NET 中的 System.Security.Cryptography 命名空间提供的 Rijndael 托管类，我们需要至少 256 位哈希。

为此，我在我的辅助类中添加了一个枚举，允许开发人员确定应该使用的 SHA 哈希，从而可以生成更大的密钥。要使用 ECDH 函数来生成用于 Rijndael 加密的有用密钥，我们需要使用 SHA256 哈希。完整的代码如下：

byte[] SecretA=null;
byte[] SecretB=null;
try
{
    ECDiffieHellmanMerkle A = new ECDiffieHellmanMerkle(ECDHAlgorithm.ECDH_384);
    ECDiffieHellmanMerkle B = new ECDiffieHellmanMerkle(ECDHAlgorithm.ECDH_384);
    A.KeyDerivationFunction = ECDHKeyDerivationFunction.HASH;
    B.KeyDerivationFunction = ECDHKeyDerivationFunction.HASH;
    A.HashAlgorithm = DerivedKeyHashAlgorithm.SHA256_ALGORITHM;
    B.HashAlgorithm = DerivedKeyHashAlgorithm.SHA256_ALGORITHM;
    SecretA = A.RetrieveSecretKey(B.PublicKey);
    SecretB = B.RetrieveSecretKey(A.PublicKey);
}
catch(Exception ex)
{
    MessageBox.Show(ex.Message,"Win32 Error Message");
}

通信双方独立派生的共享密钥（SecretA 和 SecretB）现在可以与标准 .NET 2.0 加密类一起用于加密和解密他们的消息。

//A encrypts the message with her secret key
string SecretMessage = "The owl of Minerva only flies at dusk.";
byte[] SecretMessageByteArray = Encoding.Unicode.GetBytes(SecretMessage);
string IVString = "initialV";
byte[] IVByteArray = Encoding.Unicode.GetBytes(IVString);
RijndaelManaged rijndael = new RijndaelManaged();
ICryptoTransform encryptor = rijndael.CreateEncryptor(SecretA, IVByteArray);
MemoryStream memoryStream = new MemoryStream();
CryptoStream cryptoStream =
        new CryptoStream(memoryStream, encryptor, CryptoStreamMode.Write);
cryptoStream.Write(SecretMessageByteArray, 0, SecretMessageByteArray.Length);
cryptoStream.FlushFinalBlock();
byte[] cipherText = memoryStream.ToArray();
memoryStream.Close();
cryptoStream.Close();

//B decrypts the message with his secret key
ICryptoTransform decryptor = rijndael.CreateDecryptor(SecretB, IVByteArray);
memoryStream = new MemoryStream(cipherText);
cryptoStream =
        new CryptoStream(memoryStream, decryptor, CryptoStreamMode.Read);
byte[] clearText = new byte[cipherText.Length];
int clearTextByteSize = cryptoStream.Read(clearText, 0, clearText.Length);
memoryStream.Close();
cryptoStream.Close();
this.textBox1.Text =
        Encoding.Unicode.GetString(clearText, 0, clearTextByteSize);

一些细节

为了访问 CNG API，我被迫走上了使用 P/Invoke 来进行调用的道路。这段经历让我吃尽了苦头，但尽管如此，我还是发现这是一次迷人的冒险，它帮助我理解了底层 API 的一些复杂性，并提供了我从未想过的使用 P/Invoke 调用的经验。例如，仅仅实现从公钥和私钥检索密钥的代码就需要以下代码，我将尝试解释。它实际上只使用了三个 P/Invoke 调用：BCryptImportKeyPair、BCryptSecretAgreement 和 BCryptDeriveKey。当然，关键在于细节。

此函数最初的代码只是评估包装类中的一些枚举值，并确定如何将它们转换为 P/Invoke 签名所需的相关字符串值。在 KDF_USE_SECRET_AS_HMAC_KEY_FLAG 等情况下，它实际上是一个 uint 值，我使用了包装器中其他地方定义的常量。

public byte[] RetrieveSecretKey(byte[] externalPublicKey)
{
    string keyDerivationFunction;
    uint keyDerivationFlagValue;
    switch(KDF)
    {
        case ECDHKeyDerivationFunction.HMAC:
            keyDerivationFunction = "HMAC";
            keyDerivationFlagValue = KDF_USE_SECRET_AS_HMAC_KEY_FLAG;
            break;
        default:
            keyDerivationFunction = "HASH";
            keyDerivationFlagValue = 0;
            break;
    }

    byte[] _secretKey = new Byte[0];
    uint derivedSecretByteSize;
    string KDFHash;
    switch (HASH)
    {
        case DerivedKeyHashAlgorithm.SHA1_ALGORITHM:
            KDFHash = "SHA1";
            break;
        case DerivedKeyHashAlgorithm.SHA256_ALGORITHM:
            KDFHash = "SHA256";
            break;
        case DerivedKeyHashAlgorithm.SHA384_ALGORITHM:
            KDFHash = "SHA384";
            break;
        case DerivedKeyHashAlgorithm.SHA512_ALGORITHM:
            KDFHash = "SHA512";
            break;
        default:
            KDFHash = "SHA1";
            break;
    }
    uint status=0;

BCryptImportKeyPair 简单地允许我们获取希望与之进行秘密通信的伙伴提供的公钥，并为其创建一个句柄，我们可以在 BCryptSecretAgreement 方法中使用。我使用 Marshal.AlocHGlobal 方法为我想要用作句柄的 IntPtr 值分配足够的内存，然后将其传递给 BCryptImportKeyPair P/Invoke 方法，以便用实际的公钥填充我的句柄所指向的内存。

try
{
    //discover public key size
    uint publicKeyByteSize = (uint)externalPublicKey.Length;
    //get pointer to public key
    IntPtr publicKeyHandle = Marshal.AllocHGlobal((int)publicKeyByteSize);
    status = CryptoPrimitives.BCryptImportKeyPair(_hAlgorithmProvider,
        IntPtr.Zero, PUBLIC_BLOB, ref publicKeyHandle, externalPublicKey, 
        publicKeyByteSize, 0);
    if (!CryptoPrimitives.SUCCESS_STATUS(status))
        throw new Exception();

BCryptSecretAgreement 接收我的私钥、我的伙伴提供的公钥，并返回一个句柄，该句柄是从使用 ECDH 生成的密钥协议中获得的。

//create pointer to secret agreement from private key and external public key
status = CryptoPrimitives.BCryptSecretAgreement
        (_hPrivateKey, publicKeyHandle, ref _hSecretAgreement, 0);
if (!CryptoPrimitives.SUCCESS_STATUS(status))
    throw new Exception();

一个很难弄清楚如何进行的调用是 BCryptDeriveKey。BCryptDeriveKey 必须调用两次，第一次是为了找出需要为密钥（一个字节数组）分配多少内存，第二次是为了实际给它一个值。

关于此的最棘手之处在于如何传递参数值，它是一个包含另一个结构的结构。参数值是必需的，以便指示方法使用哪种类型的哈希来生成密钥。困难在于，指定哈希的字符串值在 BCryptBuffer 结构中被标记为 PVOID 类型。在这种情况下，IntPtr 是最有可能的数据类型，但之后我必须找到一种方法来创建一个指向我的字符串值的指针，并将此传递给一个新的 IntPtr。为此，我再次使用 Marshal.AllocHGlobal 来分配一个内存位置，IntPtr 将指向该位置。然后，我必须将我的字符串转换为字符数组，并使用 Marshal.Copy 将其复制到我分配的内存位置。以这种方式创建 BCryptBuffer 值后，我必须执行类似的步骤来创建一个指向我的 BCryptBuffer 结构的 IntPtr，这次使用 Marshal.StructureToPtr，然后将其传递给 BCryptBufferDesc 结构。最后，我花了半天时间才意识到，即使文档似乎表明我需要这样做，我也无需通过 BCryptBufferDesc 的引用。这种混乱的组织方式在 P/Invoke 场景中实际上相当罕见，我只在 http://www.pinvoke.net/ 上找到了另外两个这样的例子。希望在为您处理完之后，你们中的任何一个人都不必经历同样的困境，而是可以直接重用此解决方案。

//create parameters for hash type
CryptoPrimitives.BCryptBuffer bcBuffer = new CryptoPrimitives.BCryptBuffer();
bcBuffer.BufferType = KDF_HASH_ALGORITHM;
bcBuffer.cbBuffer = (uint)((KDFHash.Length * 2) + 2);
IntPtr pvBuffer = Marshal.AllocHGlobal(KDFHash.Length * 2);
Marshal.Copy(KDFHash.ToCharArray(), 0, pvBuffer, KDFHash.Length);
bcBuffer.pvBuffer = pvBuffer;
CryptoPrimitives.BCryptBufferDesc parameters = 
        new CryptoPrimitives.BCryptBufferDesc();
parameters.cBuffers = 1;
parameters.ulVersion = BCRYPTBUFFER_VERSION;
parameters.pBuffers = Marshal.AllocHGlobal(Marshal.SizeOf(bcBuffer));
Marshal.StructureToPtr(bcBuffer, parameters.pBuffers, false);

//call BCryptDeriveKey with null parameter to find size of secret key
if (KDFHash == "SHA1")
    status = CryptoPrimitives.BCryptDeriveKey(_hAlgorithmProvider,
    keyDerivationFunction, null, null, 0, out derivedSecretByteSize, 
    keyDerivationFlagValue);
else
    status = CryptoPrimitives.BCryptDeriveKey(_hSecretAgreement,
    keyDerivationFunction, parameters, null, 0, 
    out derivedSecretByteSize, keyDerivationFlagValue);
if (!CryptoPrimitives.SUCCESS_STATUS(status))
    throw new Exception();
//set aside memory for secret key
_secretKey = new byte[derivedSecretByteSize];
//create a secret key as byte array from secret agreement
if (KDFHash == "SHA1")
    status = CryptoPrimitives.BCryptDeriveKey(_hSecretAgreement,
            keyDerivationFunction, null, _secretKey, 
            derivedSecretByteSize, out derivedSecretByteSize,
            keyDerivationFlagValue);
else
    status = CryptoPrimitives.BCryptDeriveKey(_hSecretAgreement,
    keyDerivationFunction, parameters, _secretKey, derivedSecretByteSize,
    out derivedSecretByteSize, keyDerivationFlagValue);
if (!CryptoPrimitives.SUCCESS_STATUS(status))
    throw new Exception();
}

还应该提一下关于异常处理的事情，这在 P/Invoke 实现中通常被忽略。每次调用 CNG API 都会返回一个 uint 值。我找到的最佳解决方案是评估每个返回的 uint 值，以确定调用是否成功。我使用了一组在 bcrypt.h 头文件中找到的值。如果调用失败，我将抛出一个在 catch 块中处理的异常。然后，catch 块通过进行此简单调用来抛出 Win32 错误（这是错误堆栈中的最后一个错误）：new Win32Exception()。这反过来要求我的 CryptoPrimitives 类（之所以命名为 this，是因为它包含微软称为“原始”或低级加密功能的许多函数）中的每个 P/Invoke 签名都带有以下属性-值对，以确保所有错误都被保留而不是被忽略：SetLastError = true。

catch
{
    throw new Win32Exception();
}
finally
{
    CryptoPrimitives.BCryptCloseAlgorithmProvider(_hAlgorithmProvider, 0);
    CryptoPrimitives.BCryptDestroyKey(_hPrivateKey);
    CryptoPrimitives.BCryptDestroySecret(_hSecretAgreement);
}
return _secretKey;
}

Vista 平台调用签名：参考

使用 P/Invoke 访问 C API 时，最困难的部分是确定如何最好地声明 P/Invoke 签名。我想说这更像是一门艺术而不是科学，但实际上它是令人头晕的试错过程，而不是艺术或科学。我认为我基本上都写对了，并且通过参考我写的签名，您可以节省时间和麻烦。另一方面，由于我很有可能写错了一些，如果您有时间，我将非常感谢您提供的任何更正。我最终希望能够解决整个 CNG API，并且在微软最终发布 Visual Studio Orcas 和新的托管加密类之前，也许在大家的帮助下能够成功做到这一点。无论如何，这里有一些我一直在使用的 P/Invoke 签名。尽管有各种要求，微软倾向于不发布 P/Invoke 签名，因此寻找其他人实现的签名总是很有帮助。我希望这些对您有用，因为其他开发人员发布的 P/Invoke 签名对我一直很有用。

[DllImport("Bcrypt.dll",
            CharSet = CharSet.Auto, SetLastError = true)]
public static extern uint BCryptOpenAlgorithmProvider(
ref IntPtr hAlgorithm,
string AlgId,
string Implementation,
uint Flags
);

[DllImport("Bcrypt.dll", SetLastError = true)]
public static extern uint BCryptGenerateKeyPair(
IntPtr hObject,
ref IntPtr hKey,
uint length,
uint Flags
);

[DllImport("Bcrypt.dll", SetLastError = true)]
public static extern uint BCryptFinalizeKeyPair(
IntPtr hKey,
uint Flags
);

[DllImport("Bcrypt.dll",
            CharSet = CharSet.Auto, SetLastError = true)]
public static extern uint BCryptExportKey(
IntPtr hKey,
IntPtr hExportKey,
string BlobType,
byte[] pbOutput,
uint OutputByteLength,
out uint Result,
uint Flags
);

[DllImport("Bcrypt.dll", SetLastError = true)]
public static extern uint BCryptDestroyKey(
IntPtr hKey
);

[DllImport("Bcrypt.dll", SetLastError = true)]
public static extern uint BCryptCloseAlgorithmProvider(
IntPtr hAlgorithm,
uint Flags
);

[DllImport("Bcrypt.dll", SetLastError = true)]
public static extern uint BCryptDestroySecret(
IntPtr hSecretAgreement
);

[DllImport("Bcrypt.dll", CharSet =
            CharSet.Auto, SetLastError = true)]
public static extern uint BCryptImportKeyPair(
IntPtr hAlgorithm,
IntPtr hImportKey,
string BlobType,
ref IntPtr hPublicKey,
byte[] Input,
uint InputByteLength,
uint Flags
);

[DllImport("Bcrypt.dll",
            CharSet = CharSet.Auto, SetLastError = true)]
public static extern uint BCryptSecretAgreement(
IntPtr hPrivKey,
IntPtr hPublicKey,
ref IntPtr phSecret,
uint Flags
);

[StructLayout(LayoutKind.Sequential, CharSet=CharSet.Auto)]
public class BCryptBufferDesc
{
public uint ulVersion;
public uint cBuffers;
public IntPtr pBuffers;
}

[StructLayout(LayoutKind.Sequential, CharSet = CharSet.Auto)]
public class BCryptBuffer
{
public uint cbBuffer;
public uint BufferType;
public IntPtr pvBuffer;
}

[StructLayout(LayoutKind.Sequential)]
public class BCRYPT_ECCKEY_BLOB
{
uint Magic;
uint cbKey;
}

[DllImport("Bcrypt.dll",
            CharSet = CharSet.Auto, SetLastError = true)]
public static extern uint BCryptDeriveKey(
IntPtr hSharedSecret,
string KDF,
BCryptBufferDesc ParameterList,
byte[] DerivedKey,
uint DerivedKeyByteSize,
out uint Result,
uint Flags
);

资源

对于刚开始接触 P/Invoke 的人来说，这里有一些我认为非常有帮助的文章，解释了这项技术以及如何使用它。所有这些文章都很好，但两篇 MSDN 杂志的文章尤其如此。

• 使用平台调用 作者：NetPointerIN (CodeProject)
• Essential Pinvoke 作者：Cohen Shwartz Oren (CodeProject)
• MSDN 平台调用教程
  使用 P/Invoke 从托管类调用非托管 API
• MSDN 杂志 - 使用 P/Invoke 在 C# 中调用 Win32 DLL
• MSDN 杂志 - P/Invoke 再次审视

历史

• 2007/5/1 - 阅读了 Quartz 写的非常好的加密文章，并意识到我需要对细节做一些修改才能使这篇文章具有可读性。有时，仅仅说“代码在那里，自己去看看”确实行不通。
• 2007/5/2 - 根据 Quartz 的建议，添加了一些 P/Invoke 资源。
• 2007/5/3 - 同样根据 Quartz 的建议，我添加了一些图形，将长代码片段分解成更小的块，并写了一个更有趣的文章描述。这确实有些讨好，但似乎也让文章读起来好多了。总之，我对此更满意。再次感谢 Q-man。演示效果确实有很大的不同。