Parsi Coders

درود
در این قسمت میخوام به الگوریتم معروف rsa بپردازم.
جمع اوری اطلاعات : www.parsicoders.com
در سال ۱۹۷۶ وایتفیلد دیف (Whitfield Diffie) و مارتین هلمن (Martin Hellman) دانشجویان دانشگاه استنفورد، یکی از کاربردی ترین روشهای کد کردن اطلاعات را اختراع و به ثبت رساندند. در این روش که به روش کدینگ نا متقارن (asymmetric encryption) نیز معروف است از دو کلید برای کد کردن اطلاعات استفاده می شود. (در روشهای قدیمی تر از یک کلید استفاده می شد که به آن symmetric encryption گفته می شد.) آنها مقاله خود را در یکی از شماره های سال ۱۹۷۶ مجله IEEE که با عنوان Transactions on Information Theory منتشر شده بود به چاپ رساندند که خیلی زود انقلابی در صنعت Cryptography (پنهان سازی اطلاعات) در دنیا بوجود آورد. Public Key Cryptography یا PKC به معنی استفاده از کلید عمومی برای کد کردن و پنهان کردن اطلاعات است. در این روش هر کاربر برای کد کردن و یا باز کردن کد دو کلید در اختیار دارد، یکی کلید عمومی (Public) و یکی کلید خصوصی (Private). خاصیت این روش آن است که هر کدام از این کلید ها می تواند اطلاعاتی را که کلید دیگر کد و مخفی کرده است به حالت اصل در بیاورند.

هر چند از لحاظ ریاضی کلید های Public و Private با یکدیگر ارتباط دارند اما تقریبا" محال است که کسی بتواند حتی با تجیهزات فوق العاده مدرن و صرف وقت زیاد با داشتن یکی از کلیدها، دیگری را تشخیص دهد. در واقع می توان گفت که با توجه به سطح دانش کنونی و دستگاه های کامپیوتری موجود، الگوریتم کدینگ و ارتباط میان کلیدها تقریبا" غیر قابل شکستن است. روش کار اینگونه است که هر کاربر دو کلید در دست خود دارد که یکی را در اختیار همه دوستان و اطرافیان برای خواند مطالبی که او کد کرده است قرار می دهد، این همان کلید عمومی یا Public است. حال کافی است که او برای ارسال مطالب به دیگران مطالب را با کلید خصوصی خود کد یا مخفی سازی نماید. دیگران به راحتی می توانند مطالب او را با کلید Public ای که از وی دارند با حالت اولیه بازگردانند (Decrypt) و آنها را مطالعه کنند. و یا اگر کسی بخواهد برای شما یک مطلب کد شده بفرستد با کلید Public شما آنرا کد می کند و این تنها شما و فقط شما هستنید که می توانید آنرا با کلید Private خود باز کنید و به محتوای اصلی دسترسی داشته باشید. اساس استفاده از این روش کدینگ یا مخفی سازی اطلاعات به الگوریتم مشهوری بنام Rivest Shamir Adleman یا RSA برمی‌گردد. از این الگوریتم برای تهیه کلید های مذکور، کد کردن اطلاعات، دی کد کردن یا آشکار سازی اطلاعات، تهیه امضاهای الکترونیکی و .... استفاده می شود. الگوریتم RSA پس از آنکه ران ریوست (Ron Rivest)، آدام شامیر (Adam Shamir) و لن ادلمن (Len Adleman) در سال ۱۹۷۷ آنرا بدست آوردند به این نام مشهور شد، هرچند تکنیک های اولیه آن پیشتر در سال ۱۹۷۳ توسط فردی بنام کلیفورد کوکس (Clifford Cocks) بدست آمده بود اما تا سال ۱۹۷۷ اولا" الگورتیم کاملا" محرمانه بود و ثانیا" به سادگی آنچه در زیر بیان خواهیم کرد نبود.

● تهیه کلیدهای عمومی و خصوصی بطور خلاصه روش کار برای تهیه کلیدها به شرح زیر است : ۱- دو عدد بزرگ (هر چه بزرگتر بهتر) اول به نام های p و q را انتخاب می کنیم، بهتر است این اعداد از لحاظ سایز نزدیک به یکدیگر باشند. ۲- عدد دیگری بنام n را معادل با حاصلضرب p در q تعریف می کنیم : n = p x q ۳- عدد چهارم یعنی m را معادل حاصلضرب p-۱ در q-۱ تعریف می کنیم : (m = (p-۱) x (q-۱ ۴- عدد e را که از m کوچکتر است آنگونه پیدا می کنیم که بزرگترین مقسوم علیه مشترک این دو یک باشد به عبارتی نسبت به هم اول باشند. ۵- عددی مانند d را پیدا کنید که باقیمانده حاصلضرب d در e تقسیم بر m مساوی عدد ۱ باشد، یعنی : d x e) mod m = ۱) حال پس از طی این مراحل شما می توانید از e و n بعنوان کلید عمومی و از d و n بعنوان کلید اختصاصی استفاده کنید.

● روش پنهان کردن و آشکار کردن برای کد کردن اطلاعات کافی است عدد منتصب به هر کاراکتر - مثلا" ASCII - را که در اینجا M می نامیم در فرمول زیر قرار دهید و بجای ارسال آن عدد C = Me mod n را ارسال کنید. در واقع دراینجا شما توانسته اید با کمک کلید عمومی، کاراکتر M را به C تبدیل کنید. حال گیرنده برای آشکار سازی کافی است عدد دریافتی یعنی C را با استفاده از کلید خصوصی به M تبدیل کند. برای اینکار کافی است از این فرمول استفاده کنید : M = Cd mod n ، بنابراین شما با دریافت کاراکتر کد شده C و در دست داشتن کلید خصوصی توانسته اید کاراکتر اصلی را مشخص نمایید. در اینجا بعنوان نمونه مثالی از نحوه تعریف کلید های عمومی و خصوصی خواهیم آورد. اما برای سادگی محاسبات از اختیار کردن اعداد بزرگ دوری خواهیم کرد و توجه شما را به این نکته جلب می کنیم که هرچقدر اعداد اولیه بزرگتر باشند احتمال شکستن رمز در مدت زمان محدود ناچیزتر می‌شود. ۱- ابتدا باید دو عدد اول بزرگ انتخاب کنیم که در اینجا از اعداد ساده و هم اندازه ای مانند ۱۱ و ۳ استفاده می کنیم. پس p=۱۱ , q=۳ ۲- حاصلضرب p در q که همان n است را به اینصورت خواهیم داشت : n = ۱۱ x ۳ = ۳۳ ۳- حاصلضرب p-۱ در q-۱ که همان m است را به اینصورت خواهیم داشت : m = ۱۰ x ۲ = ۲۰ ۴- برای انتخاب عدد e که نسبت به m=۲۰ اول باشد و کمتر از آن هم باشد ساده ترین گزینه یعنی عدد ۳ را انتخاب می کنیم. ۵- برای یافتن عدد d که در رابطه d x e) mod m = ۱) صادق باشد اعداد ۱,۲,۳,۴,۵ و ... را امتحان می کنیم، بنظر می رسد که عدد ۷ برای اینکار مناسب باشد چرا که ۷x۳=۲۱ باقیمانده ای معادل ۱ بر m=۲۰ دارد. حال می توانیم از زوج (۳۳,۳) بعنوان کلید عمومی و از زوج (۳۳,۷) بعنوان کلید خصوصی استفاده کنیم. حال اگر از فرمول هایی که در مطلب قبل برای کد کردن و آشکار سازی استفاده کنیم برای اعداد ۱ تا ۱۶۳۲ به جدول زیر خواهیم رسید. m : ۰ ۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹ ۱۰ ۱۱ ۱۲ ۱۳ ۱۴ ۱۵ ۱۶ c : ۰ ۱ ۸ ۲۷ ۳۱ ۲۶ ۱۸ ۱۳ ۱۷ ۳ ۱۰ ۱۱ ۱۲ ۱۹ ۵ ۹ ۴ m : ۱۷ ۱۸ ۱۹ ۲۰ ۲۱ ۲۲ ۲۳ ۲۴ ۲۵ ۲۶ ۲۷ ۲۸ ۲۹ ۳۰ ۳۱ ۳۲ c : ۲۹ ۲۴ ۲۸ ۱۴ ۲۱ ۲۲ ۲۳ ۳۰ ۱۶ ۲۰ ۱۵ ۷ ۲ ۶ ۲۵ ۳۲ بنابراین هم اکنون شما یک جدول تبدیل کد دارید که با کمک کلید عمومی اعداد صفر تا ۳۲ را به اعدادی کد شده و در همین رنج تبدیل کرده اید. اما اگر دقت کنید تعدادی از اعداد دقیقا" به همان عدد خود تبدیل شده اند که به اینها unconcealed یا مخفی نشده گفته می شود. اولآ باید بدانیم که ۰ و ۱ همواره به همین اعداد تبدیل می شوند و مطلب دیگر اینکه اگر رنج دو عدد اول ابتدایی را بزرگ در نظر بگیریم دیگر مشکلی پیش نخواهد آمد. حال کافی است فرض کنیم A=۲ ، B=۳ ، C=۴ و ... Z=۲۷ و جملات مربوطه را کد نماییم. دقت کنید که معمولا" از ۰ و ۱ برای کدینگ استفاده نمی‌شود.

در ادامه میخواهیم سورس های برای الگوریتم rsa معرفی کنم.
پیوست :

C++ RSA Encryption

کد:
using namespace System;

using namespace System::Security::Cryptography;

using namespace System::Text;

array<Byte>^ RSAEncrypt( array<Byte>^DataToEncrypt, RSAParameters RSAKeyInfo, bool DoOAEPPadding )

{

   try

   {

      //Create a new instance of RSACryptoServiceProvider.

      RSACryptoServiceProvider^ RSA = gcnew RSACryptoServiceProvider;

      //Import the RSA Key information. This only needs

      //toinclude the public key information.

      RSA->ImportParameters( RSAKeyInfo );

      //Encrypt the passed byte array and specify OAEP padding.  

      //OAEP padding is only available on Microsoft Windows XP or

      //later.  

      array<Byte>^encryptedData = RSA->Encrypt( DataToEncrypt, DoOAEPPadding );

      delete RSA;

      return encryptedData;

   }

   //Catch and display a CryptographicException  

   //to the console.

   catch ( CryptographicException^ e ) 

   {

      Console::WriteLine( e->Message );

      return nullptr;

   }

}

array<Byte>^ RSADecrypt( array<Byte>^DataToDecrypt, RSAParameters RSAKeyInfo, bool DoOAEPPadding )

{

   try

   {

      //Create a new instance of RSACryptoServiceProvider.

      RSACryptoServiceProvider^ RSA = gcnew RSACryptoServiceProvider;

      //Import the RSA Key information. This needs

      //to include the private key information.

      RSA->ImportParameters( RSAKeyInfo );

      //Decrypt the passed byte array and specify OAEP padding.  

      //OAEP padding is only available on Microsoft Windows XP or

      //later.  

      array<Byte>^decryptedData = RSA->Decrypt( DataToDecrypt, DoOAEPPadding );

      delete RSA;

      return decryptedData;

   }

   //Catch and display a CryptographicException  

   //to the console.

   catch ( CryptographicException^ e ) 

   {

      Console::WriteLine( e );

      return nullptr;

   }

}

int main()

{

   try

   {

      //Create a UnicodeEncoder to convert between byte array and string.

      UnicodeEncoding^ ByteConverter = gcnew UnicodeEncoding;

      //Create byte arrays to hold original, encrypted, and decrypted data.

      array<Byte>^dataToEncrypt = ByteConverter->GetBytes( "Data to Encrypt" );

      array<Byte>^encryptedData;

      array<Byte>^decryptedData;

      //Create a new instance of RSACryptoServiceProvider to generate

      //public and private key data.

      RSACryptoServiceProvider^ RSA = gcnew RSACryptoServiceProvider;

      //Pass the data to ENCRYPT, the public key information 

      //(using RSACryptoServiceProvider.ExportParameters(false),

      //and a boolean flag specifying no OAEP padding.

      encryptedData = RSAEncrypt( dataToEncrypt, RSA->ExportParameters( false ), false );

      //Pass the data to DECRYPT, the private key information 

      //(using RSACryptoServiceProvider.ExportParameters(true),

      //and a boolean flag specifying no OAEP padding.

      decryptedData = RSADecrypt( encryptedData, RSA->ExportParameters( true ), false );

      //Display the decrypted plaintext to the console. 

      Console::WriteLine( "Decrypted plaintext: {0}", ByteConverter->GetString( decryptedData ) );

      delete RSA;

   }

   catch ( ArgumentNullException^ ) 

   {

      //Catch this exception in case the encryption did

      //not succeed.

      Console::WriteLine( "Encryption failed." );

   }

}

Visual Baisic 6 Rsa Encryption

کد:
Attribute VB_Name = "basModExp"

Option Explicit

Option Base 0

' A VB6/VBA procedure to carry out modular exponentiation

' with examples of RSA encryption and Diffie-Hellman key exchange

' USAGE:

' Example: strResult = mpModExp("3c", "03", "face")

' computes (0x3c)^3 mod 0xface = 0x5b56

' or, in decimal, 60^3 mod 64206 = 23382

' Parameters may be hex strings of any length subject to limitations

' of VB and your computer. May take a long time!

' First published 23 September 2005.

' mpFromHex modified 13 October 2007.

' mpModExp fixed "0" issue 4 February 2009

'************************* COPYRIGHT NOTICE*************************

' This code was originally written in Visual Basic by David Ireland

' and is copyright (c) 2005-9 D.I. Management Services Pty Limited,

' all rights reserved.

' You are free to use this code as part of your own applications

' provided you keep this copyright notice intact and acknowledge

' its authorship with the words:

'   "Contains cryptography software by David Ireland of

'   DI Management Services Pty Ltd <www.di-mgt.com.au>."

' If you use it as part of a web site, please include a link

' to our site in the form

' <a href="http://www.di-mgt.com.au/crypto.html">Cryptography

' Software Code</a>

' This code may only be used as part of an application. It may

' not be reproduced or distributed separately by any means without

' the express written permission of the author.

' David Ireland and DI Management Services Pty Limited make no

' representations concerning either the merchantability of this

' software or the suitability of this software for any particular

' purpose. It is provided "as is" without express or implied

' warranty of any kind.

' The latest version of this source code can be downloaded from

' www.di-mgt.com.au/crypto.html.

' Comments and bug reports to http://www.di-mgt.com.au/contact.html

'****************** END OF COPYRIGHT NOTICE*************************

' *********

' * TESTS *

' *********

Public Function Test_mpModExp()

    Dim strResult As String

    strResult = mpModExp("3c", "03", "face")

    Debug.Print strResult & " (expected 5b56)"

    strResult = mpModExp("beef", "03", "1000000000000") ' beef^3 = beef cubed = OXO?

    Debug.Print strResult & " (expected 6A35DDD3C9CF)"

    strResult = mpModExp("beef", "03", "10000")

    Debug.Print strResult & " (expected C9CF)"

    ' Do a mini-RSA encryption with 32-bit key:

    ' Public key (n, e) = (0x5518f65d, 0x11)

    ' Private key d = 0x2309cd31

    ' Message m = 0x35b9a3cb

    ' Encrypt c = m^e mod n = 35b9a3cb^11 mod 5518f65d = 528C41E5

    ' Decrypt m' = c^e mod n = 528C41E5^2309cd31 mod 5518f65d = 35B9A3CB

    strResult = mpModExp("35b9a3cb", "11", "5518f65d")

    Debug.Print strResult & " (expected 528C41E5)"

    strResult = mpModExp("528C41E5", "2309cd31", "5518f65d")

    Debug.Print strResult & " (expected 35B9A3CB)"

End Function

Public Function Test_RSA508()

' An example of an RSA calculation using mpModExp from

' "Some Examples of the PKCS Standards",

' An RSA Laboratories Technical Note,

' Burton S. Kaliski Jr., November 1, 1993.

' RSA key is 508 bits long.

' WARNING: this may take some time!

    Dim strMod As String

    Dim strExp As String

    Dim strPri As String

    Dim strMsg As String

    Dim strSig As String

    Dim strOK As String

    Dim strVer As String

    strMod = "0A66791DC6988168" & _

        "DE7AB77419BB7FB0" & _

        "C001C62710270075" & _

        "142942E19A8D8C51" & _

        "D053B3E3782A1DE5" & _

        "DC5AF4EBE9946817" & _

        "0114A1DFE67CDC9A" & _

        "9AF55D655620BBAB"

    strExp = "010001"

    strPri = "0123C5B61BA36EDB" & _

        "1D3679904199A89E" & _

        "A80C09B9122E1400" & _

        "C09ADCF7784676D0" & _

        "1D23356A7D44D6BD" & _

        "8BD50E94BFC723FA" & _

        "87D8862B75177691" & _

        "C11D757692DF8881"

    strMsg = "1FFFFFFFFFFFF" & _

        "FFFFFFFFFFFFFFFF" & _

        "FFFFFFFFFFFFFFFF" & _

        "FFFFFFFFFF003020" & _

        "300C06082A864886" & _

        "F70D020205000410" & _

        "DCA9ECF1C15C1BD2" & _

        "66AFF9C8799365CD"

    strOK = "6DB36CB18D3475B" & _

        "9C01DB3C78952808" & _

        "0279BBAEFF2B7D55" & _

        "8ED6615987C85186" & _

        "3F8A6C2CFFBC89C3" & _

        "F75A18D96B127C71" & _

        "7D54D0D8048DA8A0" & _

        "544626D17A2A8FBE"

    ' Sign, i.e. Encrypt with private key, s = m^d mod n

    Debug.Print "Calculating signature (be patient)..."

    strSig = mpModExp(strMsg, strPri, strMod)

    Debug.Print strSig

    If strSig = strOK Then

        Debug.Print "Hooray! Signature matches."

    Else

        Debug.Print "BOO! Signature was wrong."

    End If

    ' Verify, i.e. Decrypt with public key m' = s^e mod n

    Debug.Print "Calculating verification (be patient)..."

    strVer = mpModExp(strSig, strExp, strMod)

    Debug.Print strVer

    If strVer = strMsg Then

        Debug.Print "Hooray! Verification was OK."

    Else

        Debug.Print "BOO! Verification failed."

    End If

End Function

Public Function Test_Diffie_Hellman()

    ' A very simple example of Diffie-Hellman key exchange.

    ' CAUTION: Practical use requires numbers of 1000-2000+ bits in length

    ' and other checks on suitability of p and g.

    ' EXPLANATION OF SIMPLE DIFFIE-HELLMAN

    ' 1. Both parties agree to select and share a public generator, say, g = 3

    '    and public prime modulus  p = 0xc773218c737ec8ee993b4f2ded30f48edace915f

    ' 2. Alice selects private key x = 0x849dbd59069bff80cf30d052b74beeefc285b46f

    ' 3. Alice's public key is Ya = g^x mod p. Alice sends this to Bob.

    ' 4. To send a concealed, shared secret key to Alice, Bob picks a secret random number

    '    say, y = 0x40a2cf7390f76c1f2eef39c33eb61fb11811d528

    ' 5. Bob computes Yb = g^y mod p and sends this to Alice.

    ' 6. Bob can computes the shared key k = Ya^y mod p,

    '    to use for further communications with Alice

    ' 7. Alice can compute the same shared key k = Yb^x mod p,

    '    to use for further communications with Bob.

    ' Note: k = Ya^y = (g^x)^y = g^(xy) = Yb^x = (g^y)^x = g^(xy) mod p

    ' An eavesdropper only sees g, p, Ya and Yb.

    ' It is easy to compute Y=g^x mod p but it is

    ' difficult to compute x given g^x mod p.

    ' This is the discrete logarithm problem.

    Dim Ya As String

    Dim Yb As String

    Dim Ka As String

    Dim Kb As String

    ' Alice computes Ya = g^x mod p

    Ya = mpModExp("3", "849dbd59069bff80cf30d052b74beeefc285b46f", "c773218c737ec8ee993b4f2ded30f48edace915f")

    Debug.Print "Ya = " & Ya

    ' Bob computes Yb = g^y mod p

    Yb = mpModExp("3", "40a2cf7390f76c1f2eef39c33eb61fb11811d528", "c773218c737ec8ee993b4f2ded30f48edace915f")

    Debug.Print "Yb = " & Yb

    ' Alice computes the secret key k = Yb^x mod p

    Ka = mpModExp(Yb, "849dbd59069bff80cf30d052b74beeefc285b46f", "c773218c737ec8ee993b4f2ded30f48edace915f")

    Debug.Print "Ka = " & Ka

    ' Bob computes the secret key k = Ya^y mod p

    Kb = mpModExp(Ya, "40a2cf7390f76c1f2eef39c33eb61fb11811d528", "c773218c737ec8ee993b4f2ded30f48edace915f")

    Debug.Print "Kb = " & Kb

    If Ka <> Kb Then

        Debug.Print "ERROR: keys do not match!"

    Else

        Debug.Print "Keys match OK."

    End If

End Function

' *********************

' * EXPORTED FUNCTION *

' *********************

Public Function mpModExp(strBaseHex As String, strExponentHex As String, strModulusHex As String) As String

' Computes b^e mod m given input (b, e, m) in hex format.

' Returns result as a hex string with all leading zeroes removed.

' Store numbers as byte arrays with

' least-significant byte in x[len-1]

' and most-significant byte in x[1]

' x[0] is initially zero and is used for overflow

    Dim abBase() As Byte

    Dim abExponent() As Byte

    Dim abModulus() As Byte

    Dim abResult() As Byte

    Dim nLen As Integer

    Dim n As Integer

    ' Convert hex strings to arrays of bytes

    abBase = mpFromHex(strBaseHex)

    abExponent = mpFromHex(strExponentHex)

    abModulus = mpFromHex(strModulusHex)

    ' We require all byte arrays to be the same length

    ' with the first byte left as zero

    nLen = UBound(abModulus) + 1

    n = UBound(abExponent) + 1

    If n > nLen Then nLen = n

    n = UBound(abBase) + 1

    If n > nLen Then nLen = n

    Call FixArrayDim(abModulus, nLen)

    Call FixArrayDim(abExponent, nLen)

    Call FixArrayDim(abBase, nLen)

    '''Debug.Print "b=" & mpToHex(abBase)

    '''Debug.Print "e=" & mpToHex(abExponent)

    '''Debug.Print "m=" & mpToHex(abModulus)

    ' Do the business

    abResult = aModExp(abBase, abExponent, abModulus, nLen)

    ' Convert result to hex

    mpModExp = mpToHex(abResult)

    '''Debug.Print "r=" & mpModExp

    ' Strip leading zeroes

    For n = 1 To Len(mpModExp)

        If Mid$(mpModExp, n, 1) <> "0" Then

            Exit For

        End If

    Next

    ' FIX: [2009-02-04] Changed from >= to >

    If n > Len(mpModExp) Then

        ' Answer is zero

        mpModExp = "0"

    ElseIf n > 1 Then

        ' Zeroes to strip

        mpModExp = Mid$(mpModExp, n)

    End If

End Function

' **********************

' * INTERNAL FUNCTIONS *

' **********************

Public Function aModExp(abBase() As Byte, abExponent() As Byte, abModulus() As Byte, nLen As Integer) As Variant

' Computes a = b^e mod m and returns the result in a byte array as a VARIANT

    Dim a() As Byte

    Dim e() As Byte

    Dim s() As Byte

    Dim nBits As Long

    ' Perform right-to-left binary exponentiation

    ' 1. Set A = 1, S = b

    ReDim a(nLen - 1)

    a(nLen - 1) = 1

    ' NB s and e are trashed so use copies

    s = abBase

    e = abExponent

    ' 2. While e != 0 do:

    For nBits = nLen * 8 To 1 Step -1

        ' 2.1 if e is odd then A = A*S mod m

        If (e(nLen - 1) And &H1) <> 0 Then

            a = aModMult(a, s, abModulus, nLen)

        End If

        ' 2.2 e = e / 2

        Call DivideByTwo(e)

        ' 2.3 if e != 0 then S = S*S mod m

        If aIsZero(e, nLen) Then Exit For

        s = aModMult(s, s, abModulus, nLen)

        DoEvents

    Next

    ' 3. Return(A)

    aModExp = a

End Function

Private Function aModMult(abX() As Byte, abY() As Byte, abMod() As Byte, nLen As Integer) As Variant

' Returns w = (x * y) mod m

    Dim w() As Byte

    Dim x() As Byte

    Dim y() As Byte

    Dim nBits As Integer

    ' 1. Set w = 0, and temps x = abX, y = abY

    ReDim w(nLen - 1)

    x = abX

    y = abY

    ' 2. From LS bit to MS bit of X do:

    For nBits = nLen * 8 To 1 Step -1

        ' 2.1 if x is odd then w = (w + y) mod m

        If (x(nLen - 1) And &H1) <> 0 Then

            Call aModAdd(w, y, abMod, nLen)

        End If

        ' 2.2 x = x / 2

        Call DivideByTwo(x)

        ' 2.3 if x != 0 then y = (y + y) mod m

        If aIsZero(x, nLen) Then Exit For

        Call aModAdd(y, y, abMod, nLen)

    Next

    aModMult = w

End Function

Private Function aIsZero(a() As Byte, ByVal nLen As Integer) As Boolean

' Returns true if a is zero

    aIsZero = True

    Do While nLen > 0

        If a(nLen - 1) <> 0 Then

            aIsZero = False

            Exit Do

        End If

        nLen = nLen - 1

    Loop

End Function

Private Sub aModAdd(a() As Byte, b() As Byte, m() As Byte, nLen As Integer)

' Computes a = (a + b) mod m

    Dim i As Integer

    Dim d As Long

    ' 1. Add a = a + b

    d = 0

    For i = nLen - 1 To 0 Step -1

        d = CLng(a(i)) + CLng(b(i)) + d

        a(i) = CByte(d And &HFF)

        d = d \ &H100

    Next

    ' 2. If a > m then a = a - m

    For i = 0 To nLen - 2

        If a(i) <> m(i) Then

            Exit For

        End If

    Next

    If a(i) >= m(i) Then

        Call aSubtract(a, m, nLen)

    End If

    ' 3. Return a in-situ

End Sub

Private Sub aSubtract(a() As Byte, b() As Byte, nLen As Integer)

' Computes a = a - b

    Dim i As Integer

    Dim borrow As Long

    Dim d As Long   ' NB d is signed

    borrow = 0

    For i = nLen - 1 To 0 Step -1

        d = CLng(a(i)) - CLng(b(i)) - borrow

        If d < 0 Then

            d = d + &H100

            borrow = 1

        Else

            borrow = 0

        End If

        a(i) = CByte(d And &HFF)

    Next

End Sub

Private Sub DivideByTwo(ByRef x() As Byte)

' Divides multiple-precision integer x by 2 by shifting to right by one bit

    Dim d As Long

    Dim i As Integer

    d = 0

    For i = 0 To UBound(x)

        d = d Or x(i)

        x(i) = CByte((d \ 2) And &HFF)

        If (d And &H1) Then

            d = &H100

        Else

            d = 0

        End If

    Next

End Sub

Public Function mpToHex(abNum() As Byte) As String

' Returns a string containg the mp number abNum encoded in hex

' with leading zeroes trimmed.

    Dim i As Integer

    Dim sHex As String

    sHex = ""

    For i = 0 To UBound(abNum)

        If abNum(i) < &H10 Then

            sHex = sHex & "0" & Hex(abNum(i))

        Else

            sHex = sHex & Hex(abNum(i))

        End If

    Next

    mpToHex = sHex

End Function

Public Function mpFromHex(ByVal strHex As String) As Variant

' Converts number encoded in hex in big-endian order to a multi-precision integer

' Returns an array of bytes as a VARIANT

' containing number in big-endian order

' but with the first byte always zero

' strHex must only contain valid hex digits [0-9A-Fa-f]

' [2007-10-13] Changed direct >= <= comparisons with strings.

    Dim abData() As Byte

    Dim ib As Long

    Dim ic As Long

    Dim ch As String

    Dim nch As Long

    Dim nLen As Long

    Dim t As Long

    Dim v As Long

    Dim j As Integer

    ' Cope with odd # of digits, e.g. "fed" => "0fed"

    If Len(strHex) Mod 2 > 0 Then

        strHex = "0" & strHex

    End If

    nLen = Len(strHex) \ 2 + 1

    ReDim abData(nLen - 1)

    ib = 1

    j = 0

    For ic = 1 To Len(strHex)

        ch = Mid$(strHex, ic, 1)

        nch = Asc(ch)

        ''If ch >= "0" And ch <= "9" Then

        If nch >= &H30 And nch <= &H39 Then

            ''t = Asc(ch) - Asc("0")

            t = nch - &H30

        ''ElseIf ch >= "a" And ch <= "f" Then

        ElseIf nch >= &H61 And nch <= &H66 Then

            ''t = Asc(ch) - Asc("a") + 10

            t = nch - &H61 + 10

        ''ElseIf ch >= "A" And ch <= "F" Then

        ElseIf nch >= &H41 And nch <= &H46 Then

            ''t = Asc(ch) - Asc("A") + 10

            t = nch - &H41 + 10

        Else

            ' Invalid digit

            ' Flag error?

            Debug.Print "ERROR: Invalid Hex character found!"

            Exit Function

        End If

        ' Store byte value on every alternate digit

        If j = 0 Then

            ' v = t << 8

            v = t * &H10

            j = 1

        Else

            ' b[i] = (v | t) & 0xff

            abData(ib) = CByte((v Or t) And &HFF)

            ib = ib + 1

            j = 0

        End If

    Next

    mpFromHex = abData

End Function

Private Sub FixArrayDim(ByRef abData() As Byte, ByVal nLen As Long)

' Redim abData to be nLen bytes long with existing contents

' aligned at the RHS of the extended array

    Dim oLen As Long

    Dim i As Long

    oLen = UBound(abData) + 1

    If oLen > nLen Then

        ' Truncate

        ReDim Preserve abData(nLen - 1)

    ElseIf oLen < nLen Then

        ' Shift right

        ReDim Preserve abData(nLen - 1)

        For i = oLen - 1 To 0 Step -1

            abData(i + nLen - oLen) = abData(i)

        Next

        For i = 0 To nLen - oLen - 1

            abData(i) = 0

        Next

    End If

End Sub

Public Function TestConvFromHex()

    Dim abData() As Byte

    abData = mpFromHex("deadbeef")

    Debug.Print mpToHex(abData)

    abData = mpFromHex("FfeE01")

    Debug.Print mpToHex(abData)

    abData = mpFromHex("1")

    Debug.Print mpToHex(abData)

End Function

Amin_Mansouri

Amin_Mansouri

Amin_Mansouri