RSA64

[Antonariy]

В целях защиты от копирования хочу использовать сабж. Нашел алгоритм кодирования/декодирования, но без генерации ключей. В код вставлены уже вычисленные ключи. Там есть комменты на инглише, вкратце описывающие как их генерить, однако в смысл комментов я так и не въехал. Может кто-нибудь сможет объяснить на пальцах?

[Konst_One]

вот здесь глянь:
http://www.pbcrypto.com/algorithms/source/

там есть модуль rsa64.bas, в котором есть метод keygen() там поподробнее расписан метод генерации E и D

[Konst_One]

Код: Выделить всё


'**************************************
'Windows API/Global Declarations for :Fa
'     st 64bit RSA Encryption Algorithm
'**************************************
Public key(1 To 3) As Double
Public p As Double, q As Double
Public PHI As Double


Public Sub keyGen()
    'Generates the keys for E, D and N
    Dim E#, D#, N#
    Const PQ_UP As Integer = 9999 'set upper limit of random number
    Const PQ_LW As Integer = 3170 'set lower limit of random number
    Const KEY_LOWER_LIMIT As Long = 10000000 'set for 64bit minimum
    p = 0: q = 0
    Randomize


    Do Until D > KEY_LOWER_LIMIT 'makes sure keys are 64bit minimum


        Do Until IsPrime(p) And IsPrime(q) ' make sure q and q are primes
            p = Int((PQ_UP - PQ_LW + 1) * Rnd + PQ_LW)
            q = Int((PQ_UP - PQ_LW + 1) * Rnd + PQ_LW)
        Loop
        N = p * q
        PHI = (p - 1) * (q - 1)
        E = GCD(PHI)
        D = Euler(E, PHI)
    Loop
    key(1) = E
    key(2) = D
    key(3) = N
   
End Sub


Private Function Euler(E3 As Double, PHI3 As Double) As Double
    'genetates D from (E and PHI) using the
    '     Euler algorithm
    On Error Resume Next
    Dim u1#, u2#, u3#, v1#, v2#, v3#, q#
    Dim t1#, t2#, t3#, z#, uu#, vv#, inverse#
    u1 = 1
    u2 = 0
    u3 = PHI3
    v1 = 0
    v2 = 1
    v3 = E3


    Do Until (v3 = 0)
        q = Int(u3 / v3)
        t1 = u1 - q * v1
        t2 = u2 - q * v2
        t3 = u3 - q * v3
        u1 = v1
        u2 = v2
        u3 = v3
        v1 = t1
        v2 = t2
        v3 = t3
        z = 1
    Loop
    uu = u1
    vv = u2


    If (vv < 0) Then
        inverse = vv + PHI3
    Else
        inverse = vv
    End If
    Euler = inverse
End Function


Private Function GCD(nPHI As Double) As Double
    'generates a random number relatively pr
    '     ime to PHI
    On Error Resume Next
    Dim nE#, y#
    Const N_UP = 99999999 'set upper limit of random number for E
    Const N_LW = 10000000 'set lower limit of random number for E
    Randomize
    nE = Int((N_UP - N_LW + 1) * Rnd + N_LW)
    top:
    x = nPHI Mod nE
    y = x Mod nE


    If y <> 0 And IsPrime(nE) Then
        GCD = nE
        Exit Function
    Else
        nE = nE + 1
    End If
   
    GoTo top
End Function


Private Function IsPrime(lngNumber As Double) As Boolean
    'Returns 'True' if lngNumber is a prime
   
    On Error Resume Next
    Dim lngCount#
    Dim lngSqr#
    Dim x#
    lngSqr = Int(Sqr(lngNumber)) ' Get the int square root


    If lngNumber < 2 Then
        IsPrime = False
        Exit Function
    End If
    lngCount = 2
    IsPrime = True


    If lngNumber Mod lngCount = 0 Then
        IsPrime = False
        Exit Function
    End If
    lngCount = 3


    For x = lngCount To lngSqr Step 2


        If lngNumber Mod x = 0 Then
            IsPrime = False
            Exit Function
        End If
    Next
End Function


Public Function Mult(ByVal x As Double, ByVal p As Double, ByVal m As Double) As Double
    'encrypts, decrypts values passed to the


'     function.. e.g.
    'Mult = M^E mod N (encrypt) where M = x
    '     , E = p, N = m
    'Mult = M^D mod N (decrypt)
    On Error GoTo error1
   
    y = 1
   


    Do While p > 0


        Do While (p / 2) = Int((p / 2))
            x = nMod((x * x), m)
            p = p / 2
        Loop
        y = nMod((x * y), m)
        p = p - 1
    Loop
    Mult = y
    Exit Function
    error1:
    y = 0
End Function


Private Function nMod(x As Double, y As Double) As Double
    'this function replaces the Mod command.
    '     instead of z = x Mod y
    'it is now z = nMod(x,y)
    On Error Resume Next
    Dim z#
    z = x - (Int(x / y) * y)
    nMod = z
End Function


Public Function enc(tIp As String, eE As Double, eN As Double) As String
    'returns the long value of the character
    '     s, chained with a +
    'e.g. 12345678+23456789+ etc..
    '**Taken out encryption algorithm to sim
    '     plify program**
    On Error Resume Next
    Dim encSt As String
    encSt = ""
    e2st = ""
   
    If tIp = "" Then Exit Function


    For i = 1 To Len(tIp)
        encSt = encSt & Mult(CLng(Asc(Mid(tIp, i, 1))), eE, eN) & "+"
    Next i
    '** put your encryption algorithm code h
    '     ere **
    enc = encSt
   
End Function


Public Function dec(tIp As String, dD As Double, dN As Double) As String
    'returns the characters from the long va
    '     lues
    'e.g A = 12345678, B = 23456789 etc..
    '**Taken out decryption algorithm to sim
    '     plify program**
    On Error Resume Next
    Dim decSt As String
    decSt = ""
    '** put your decryption algorithm code h
    '     ere **


    For z = 1 To Len(tIp)
        ptr = InStr(z, tIp, "+")
        tok = Val(Mid(tIp, z, ptr))
        decSt = decSt + Chr(Mult(tok, dD, dN))
        z = ptr
    Next z
    dec = decSt
End Function
      

[Antonariy]

Блин, я ведь натыкался на этот модуль где-то на другом сайте...
Пора на пенсию

[eugene2005]

#COMPILE EXE
#INCLUDE "win32api.inc"
GLOBAL key() AS DOUBLE
GLOBAL p AS DOUBLE, q AS DOUBLE
GLOBAL PHI AS DOUBLE

DECLARE FUNCTION dec(tIp AS STRING, dD AS DOUBLE, dN AS DOUBLE) AS STRING
DECLARE FUNCTION enc(tIp AS STRING, eE AS DOUBLE, eN AS DOUBLE) AS STRING
DECLARE FUNCTION nMod(x AS DOUBLE, y AS DOUBLE) AS DOUBLE
DECLARE FUNCTION Mult(BYVAL x AS DOUBLE, BYVAL p AS DOUBLE, BYVAL m AS DOUBLE) AS DOUBLE
DECLARE FUNCTION IsPrime(lngNumber AS DOUBLE) AS BYTE
DECLARE FUNCTION GCD(nPHI AS DOUBLE) AS DOUBLE
DECLARE FUNCTION Euler(E3 AS DOUBLE, PHI3 AS DOUBLE) AS DOUBLE
DECLARE SUB keyGen()

SUB keyGen()
'Generates the keys for E, D and N
DIM E#, D#, N#
%PQ_UP = 9999 'set upper limit of random number
%PQ_LW = 3170 'set lower limit of random number
%KEY_LOWER_LIMIT = 10000000 'set for 64bit minimum
p = 0: q = 0
RANDOMIZE TIMER
DO UNTIL D > %KEY_LOWER_LIMIT 'makes sure keys are 64bit minimum
DO UNTIL IsPrime(p) AND IsPrime(q) ' make sure q and q are primes
p = INT((%PQ_UP - %PQ_LW + 1) * RND + %PQ_LW)
q = INT((%PQ_UP - %PQ_LW + 1) * RND + %PQ_LW)
LOOP
N = p * q
PHI = (p - 1) * (q - 1)
E = GCD(PHI)
D = Euler(E, PHI)
LOOP
key(1) = E
key(2) = D
key(3) = N
END SUB

FUNCTION Euler(E3 AS DOUBLE, PHI3 AS DOUBLE) AS DOUBLE
'genetates D from (E and PHI) using the Euler algorithm
ON ERROR RESUME NEXT
DIM u1#, u2#, u3#, v1#, v2#, v3#, q#
DIM t1#, t2#, t3#, z#, uu#, vv#, inverse#
u1 = 1
u2 = 0
u3 = PHI3
v1 = 0
v2 = 1
v3 = E3
DO UNTIL (v3 = 0)
q = INT(u3 / v3)
t1 = u1 - q * v1
t2 = u2 - q * v2
t3 = u3 - q * v3
u1 = v1
u2 = v2
u3 = v3
v1 = t1
v2 = t2
v3 = t3
z = 1
LOOP
uu = u1
vv = u2
IF (vv < 0) THEN
inverse = vv + PHI3
ELSE
inverse = vv
END IF
Euler = inverse
END FUNCTION

FUNCTION GCD(nPHI AS DOUBLE) AS DOUBLE
'generates a random number relatively prime to PHI
ON ERROR RESUME NEXT
DIM nE#, y#
DIM x AS DOUBLE
%N_UP = 99999999 'set upper limit of random number for E
%N_LW = 10000000 'set lower limit of random number for E
RANDOMIZE
nE = INT((%N_UP - %N_LW + 1) * RND + %N_LW)
top:
x = nPHI MOD nE
y = x MOD nE
IF y <> 0 AND IsPrime(nE) THEN
GCD = nE
EXIT FUNCTION
ELSE
nE = nE + 1
END IF
GOTO top
END FUNCTION
FUNCTION IsPrime(lngNumber AS DOUBLE) AS BYTE
'Returns '%TRUE' if lngNumber is a prime
ON ERROR RESUME NEXT
DIM lngCount#
DIM lngSqr#
DIM x#
lngSqr = INT(SQR(lngNumber)) ' Get the int square root
IF lngNumber < 2 THEN
IsPrime = %FALSE
EXIT FUNCTION
END IF
lngCount = 2
IsPrime = %TRUE
IF lngNumber MOD lngCount = 0 THEN
IsPrime = %FALSE
EXIT FUNCTION
END IF
lngCount = 3
FOR x = lngCount TO lngSqr STEP 2
IF lngNumber MOD x = 0 THEN
IsPrime = %FALSE
EXIT FUNCTION
END IF
NEXT
END FUNCTION

FUNCTION Mult(BYVAL x AS DOUBLE, BYVAL p AS DOUBLE, BYVAL m AS DOUBLE) AS DOUBLE
DIM y AS DOUBLE
'encrypts, decrypts values passed to the function.. e.g.
'Mult = M^E mod N (encrypt) where M = x , E = p, N = m
'Mult = M^D mod N (decrypt)
ON ERROR GOTO error1
y = 1
DO WHILE p > 0
DO WHILE (p / 2) = INT((p / 2))
x = nMod((x * x), m)
p = p / 2
LOOP
y = nMod((x * y), m)
p = p - 1
LOOP
Mult = y
EXIT FUNCTION
error1:
y = 0
END FUNCTION

FUNCTION nMod(x AS DOUBLE, y AS DOUBLE) AS DOUBLE
'this function replaces the Mod command. instead of z = x Mod y
'it is now z = nMod(x,y)
ON ERROR RESUME NEXT
DIM z#
z = x - (INT(x / y) * y)
nMod = z
END FUNCTION

FUNCTION GoHex(xLng AS LONG) AS STRING
ON ERROR RESUME NEXT
DIM I AS LONG
DIM xStr AS STRING
DIM OutStr$
xStr = RIGHT$("00000000" & TRIM$(STR$(xLng)),
FOR I = 1 TO LEN(xStr)
OutStr$ = OutStr$ & CHR$(VAL("&h" & MID$(xStr, I, 2)))
! inc I
NEXT I
FUNCTION = OutStr$
END FUNCTION
FUNCTION enc(tIp AS STRING, eE AS DOUBLE, eN AS DOUBLE) AS STRING
ON ERROR RESUME NEXT
DIM encSt AS STRING
DIM e2st AS STRING
DIM I AS LONG
encSt = ""
e2st = ""
IF tIp = "" THEN EXIT FUNCTION
FOR i = 1 TO LEN(tIp)
encSt = encSt & GoHex(Mult(CLNG(ASC(MID$(tIp, i, 1))), eE, eN))
NEXT i
enc = encSt
END FUNCTION

FUNCTION dec(tIp AS STRING, dD AS DOUBLE, dN AS DOUBLE) AS STRING
ON ERROR RESUME NEXT
DIM decSt AS STRING
DIM z AS LONG
DIM zptr AS LONG
DIM sTmp AS STRING
DIM tok AS LONG
decSt = ""
FOR z = 1 TO LEN(tIp)
sTmp = sTmp & HEX$(ASC(MID$(tIp,z,1)),2)
sTmp = sTmp & HEX$(ASC(MID$(tIp,z+1,1)),2)
sTmp = sTmp & HEX$(ASC(MID$(tIp,z+2,1)),2)
sTmp = sTmp & HEX$(ASC(MID$(tIp,z+3,1)),2)
tok = VAL(sTmp)
decSt = decSt + CHR$(Mult(tok, dD, dN))
! add z, 3
sTmp = ""
NEXT z
dec = decSt
END FUNCTION


'/////////////////////////////////////////////////////
'// Demo program - creates private and public keys, //
'// then encrypts and decrypts a test string. //
'/////////////////////////////////////////////////////
FUNCTION PBMAIN() AS LONG
REDIM key(3) AS DOUBLE
DIM EncStr AS STRING
DIM DecStr AS STRING
DIM PlainText AS STRING
PlainText = "ABCDEFGHIJKLMNOPQRSTUVWXYZ 1234567890" 'The message to encrypt
keyGen
STDOUT "Result:"
STDOUT " p=" & STR$(p)
STDOUT " q=" & STR$(q)
STDOUT " PHI=" & STR$(PHI)
STDOUT " E=" & LEFT$(STR$(Key(1)) & SPACE$(12),12) & "PRIVATE KEY"
STDOUT " D=" & LEFT$(STR$(Key(2)) & SPACE$(12),12) & "PUBLIC KEY"
STDOUT " N=" & LEFT$(STR$(Key(3)) & SPACE$(12),12) & "PUBLIC KEY"
STDOUT
STDOUT "Plaintext: " & PlainText
EncStr = enc(Plaintext, key(1), key(3))
STDOUT "Encrypted: " & EncStr
DecStr = dec(EncStr, key(2), key(3))
STDOUT "Decrypted: " & DecStr
WAITKEY$
END FUNCTION

[Antonariy]

Тут 3 ключа

Код: Выделить всё

Public key(1 To 3) As Double

1й открытый, 2й закрытый, 3й общий. Для шифрации 2+3, для дешифрации 1+3.

[eugene2005]

а чтоб увеличить ключ до 512 действительно надо 512/64?

[Antonariy]

Вообще-то вся идеология RSA основана именно на том, что по одному ключу невозможно вычислить второй, потому что за основу их вычисления берутся два произвольных простых числа никак между собой не связанные.
В принципе я в криптографии не копенгаген, но судя по тому, что написано тут:
http://algolist.manual.ru/defence/attack/rsa.php
все так и есть.
Кстати, какой из ключей (1, 2) отрытый, а какой закрытый, совершенно без разницы, это тоже фича RSA.

[Antonariy]

http://bugtraq.ru/library/crypto/rsa.html
Вот еще интересное чтиво.

[alibek]

Народ, а почему вы так CAPICOM не любите?

[Antonariy]

Что за зверь?

[alibek]

API, предоставляющее криптографические службы.
http://msdn.microsoft.com/library/defau ... erence.asp

Кроме того, часть функций описана в API-Guide, в категории Crypto. Не уверен, правда, что они относятся к CAPICOM, но их тоже можно использовать.

[Antonariy]

Ага, вот первая причина не любить: в дистрибутив виндов, в отличие от, к примеру, CryptEncrypt Lib "advapi32.dll", не входит, нужно скачивать, устанавливать и таскать с собой.
Вторая причина - скачать могут только владельцы лицензионных виндов, а я снес предустановленную лицензионную Home и поставил Pro, известно какую.

Может у тебя есть уже скачанный капиком?
Примеры в нете нашел.

[alibek]

Сам CAPICOM не требует лицензионности системы.
Кто-то наверняка скачал до того, как ввели WGA, поищи в инете.

[SergT]

Я только что скачал (1.3 Мб). Сказали, что у меня полинная W2000... Ну и слава Богу! Нужно?

[Antonariy]

FleX_2004
Забыл про fls <> 9

Из функции euler можно убрать z и uu.

У меня ошибок не возникает, только ключи генерятся непристойно долго. Какие значения констант используешь?

[Antonariy]

Тут переводить нечего. Лажа какая-то... Типа проверка сгенеренных ключей. Лучше надыбь листинг функции RSA_generate_key.

[kif]

меняю класс и dll (RSA с длиной ключа 2048) на библиотечку, создающую TIFF F (для факса).

[Antonariy]

из чего создающую?

[kif]

создающую пару ключей (с сохранением), шифрующую, расшифровывающую и подписывающую сообщение

[kif]

и проверяющую подпись, соответственно

[kif]

из bmp, jpg или другого tiff не являющимся tiff f. и чтобы файл был без зжатия.