PowerBASIC Forums
  Programming
  Public key cryptography (Page 1)

Post New Topic  Post A Reply
profile | register | preferences | faq | search

UBBFriend: Email This Page to Someone!
This topic is 2 pages long:   1  2 
next newest topic | next oldest topic
Author Topic:   Public key cryptography
Wayne Diamond
Member
posted July 31, 2001 09:53 AM     Click Here to See the Profile for Wayne Diamond     Edit/Delete Message   Reply w/Quote
Mid$(TextStr$, i, 1) = CHR$(ASC(Mid$(TextStr$, i, 1)) XOR 13)

That's a good (by good, i mean simple!) example of a symmetric cipher, symmetric meaning the same key (in this case xor 13) can be used to both encrypt and decrypt data.
Does anyone have any simple examples of ASSYMETRIC/"public-key" encryption? Emphasis on simple im more looking into the theory than actual cipher strength, so the simpler the better, but this one is taxing my brain

------------------

IP: Logged

Aldo Cavini
Member
posted July 31, 2001 11:20 PM     Click Here to See the Profile for Aldo Cavini     Edit/Delete Message   Reply w/Quote
The following is from an old DOS program. I don't know whether it is an ASSYMETRIC/"public-key" encryption method, since I "invented" it from scratch - at least it is guaranteed it works!

%CryptAdd = 134
%CryptMul = 17

sub Encrypt( s$ )

local i%, ch%

for i% = 1 to len( s$ )
ch% = ( 256 - %CryptAdd + asc( mid$( s$, i% ) ) ) and 255
mid$( s$, i% ) = chr$( ( ( ch% + ( %CryptMul - ( ch% mod %CryptMul ) ) * 256 ) / %CryptMul ) and 255 )
next
end sub

sub Decrypt( s$ )

local i%

for i% = 1 to len( s$ )
mid$( s$, i% ) = chr$( ( asc( mid$( s$, i% ) ) * %CryptMul + %CryptAdd ) and 255 )
next

end sub

I needed Decrypt to be the fastest of the two. It simply gets a char, multiplyes it for a constant (constant must be a prime number), adds it an offset and truncates it to an 8 bit value. The other sub somehow performs the reverse.

------------------

[This message has been edited by Aldo Cavini (edited July 31, 2001).]

IP: Logged

Scott Turchin
Member
posted August 01, 2001 06:24 AM     Click Here to See the Profile for Scott Turchin     Edit/Delete Message   Reply w/Quote
I don't know if this falls under it or not, since it pretty much uses one key....


KeyLen = Len(wKeystring)
For Initi = 0 To 255
s(Initi) = Initi
Incr KeyCount
k(Initi) = Asc(wKeystring, KeyCount)
If KeyCount => KeyLen Then KeyCount = 0
Next
For Initi = 0 To 255
Initj = (Initj + s(Initi) + k(Initi)) Mod 256
Swap s(Initi), s(Initj)
Next
i = 0
j = 0

'Don't modify original string
'fromEncPos = 1
fromEncPos = 0
p = StrPtr(St)
pp = StrPtr(St)
For x = 0 To Len(St)-1
'c = ASC(toEnc, x)
c = @p[x]
i = (i + 1) Mod 256
j = (j + s(i)) Mod 256
Swap s(i), s(j)
t = (s(i) + s(j)) Mod 256
k = s(t)

@pp[fromEncPos] = c Xor k
Incr fromEncPos
Next
'MID$(fromEnc, fromEncPos) = RBuff
Function = St
Erase s
Erase k


------------------
Scott

IP: Logged

Tim Wisseman
unregistered
posted August 01, 2001 08:02 AM           Edit/Delete Message   Reply w/Quote
This is how one form of public key encryption works.

I run my make key program:

MakeKey
Public = 13, 78
Private = 78, 13

I have a public key of 13,78 and a private key of 78,13

My friend Bob, wants to send me a message the text of which is
"h" He takes the message and my public key and
encrypts it like so:

ENCRYPT "h" , 13, 78
Message = 179

Now Bob sends me the message, but sneaky Bill intercepts
the message. Sneaky Bill has my public key and the encrypter
and decrypter programs so he tries the public key with both
programs. . .

ENCRYPT 179 , 13, 78
Message = ASC(13)

DECRYPT 179 , 13, 78
Message = ASC(21)

Sneaky Bill has been foiled!

I get the message and decrypt it using my private key:

DECRYPT 179 , 78, 13
Message = "h"

Oh yes! "h" I will get on it at once!

The power of public key encryption is in the vast amount
of CPU time required to figure out what the private key
is given the public key and the encryption algorithom. The more
complex the relationship between the public key and the
private key the better.

I bet you can figure out what the relationship of my public
and private keys are by just looking at the above example, no CPU
needed.

The CIA might intercept my message and just run my
public key through their SuperKeyCracker2000

SuperKeyCracker2000 13, 78
Private Key = 78, 13

Drats! The CIA can now read my secret messages! I think I might
need a stronger encryption system!

Now some source code to play with:

DIM sMess AS STRING
DIM iMess AS INTEGER
DIM a AS INTEGER
DIM b AS INTEGER
DIM i AS INTEGER

'// The message we are sending is just "h"
sMess = "h"
iMess = ASC(sMess)

'// Public Key = 13 and 78
a = 13
b = 78
i = iMess XOR a
i = (i + b) MOD 255

'// Your secret message (It will be 179)
PRINT "Your message is: "; STR$(i)


'// Your incoming message is 179
iMess = 179
'// Private Key = 78 And 13
a = 78
b = 13
i = (iMess - a) MOD 255
i = i XOR b
sMess = CHR$(i)
PRINT "decoded message is: "; sMess


------------------

[This message has been edited by Tim Wisseman (edited August 01, 2001).]

IP: Logged

Wayne Diamond
Member
posted August 01, 2001 08:47 AM     Click Here to See the Profile for Wayne Diamond     Edit/Delete Message   Reply w/Quote
Aldo, Scott, those are both symetric algorithms - to decrypt the encrypted data, you just reapply the same algorithm with the same key. Its easier to understand in a diagram -

Symetric encryption:
Encrypted = Plaintext -> Crypt(Key)
Decrypted = Encrypted -> Crypt(Key)

but with Assymetric encryption, you have one key to encrypt, and a different key to decrypt.
Easy in concept, but what's got me confused is the actual workings of the algorithm, and Timm i think you've hit the nail on the head there! Many thanks kind sir for taking the time to write that excellent description (for some reason I was getting nowhere reading RSA documentation )
Ive printed out your post so i can be re-read it tonight before my eyes give in to sleep

The reason why I asked is because a shareware program of mine which uses symetric encryption on its keyfiles was recently cracked - these guys (a 31337 Russian outfit, possibly one of Semens mates? ) made a KEYGEN! And the keys are based on the PC1 128-bit encryption algo (not a simple serial that can be sniffed from memory), but these guys wrote a keygen no worries so that was a big wake-up call for me. I was really impressed and contacted the cracker to both congratulate and query him (you can go a long way if you speak nicely to them), and we've been exchanging emails, he's a very polite bloke (and needless to say, very confident in himself) and it was he who suggested asymetric encryption as a means of slowing down crackers. He also suggested building in checks to the keyfile that aren't compiled. When the keyfile is cracked, uncomment another check in your code. I feel totally defeated though, it really is pointless even building in any form of protection when there is nothing physically stopping smart guys like this from disassembling your code. Compiled code reads like a book to them, it's kinda scary...

Thanks again,
Wayne

------------------

IP: Logged

Wayne Diamond
Member
posted August 01, 2001 08:57 AM     Click Here to See the Profile for Wayne Diamond     Edit/Delete Message   Reply w/Quote
Here's some of what the cracker had to say, pasted here so others can get into the mind of a cracker:
(FWIW: The program is a 2mb executable compiled in VB6, compressed down to 600kb with ASPack, and has a lot of built in protection code, anti-softice etc)

Anyway, your program was not hard to crack since it relies on some symmetric encryption algorithm. First part of the process was
unpacking, really simple since a lot of tools exist for that. Then removing the SoftIce check, simply by replacing SICE by XXXX in the unpacked program,
then removing the size checks by breaking on rtcFileLen and patching in unpacked program. Then the program would run like a charm, and can be quite
easily reversed. Breaking on rtcFileLen, I had the good size of a valid keyfile, then creating and 4192bytes keyfile, I could trace through the
registration checking area. The encryption algorithm was quite simple to reverse, and I had it turned to C within 2 hours or so. The longest part was to
check what are the encrypted strings in the keyfile and how they are checked, it took me a few hours. So to conclude, it took some time, but no real
difficulty, except the fact that is Visual Basic, which stops easily crackers since the generated code is really a mess. The tools used were SoftICE to
trace, IDA to disassemble, HIEW to patch the few needed bytes, and CASPR to unpack.

And when I asked him about encrypting the already-encrypted keyfiles:
Once the algorythm reversed, and knowing I can used any key to encrypt a keyfile since it's shipped with the keyfile, the only things I have to do are:
1) create a valid unencrypted keyfile,
2) generate a random key,
3) encrypt the keyfile with this key,
4) give the user both key and keyfile.
Even if the key is not random, but checked within the executable (not 'clear' comparison, but some one-way stuff like getting the MD5 of the key and
comparing it with a hardcoded MD5, in that way you cannot get the key from the hash), getting a valid key/keyfile would allow to make a generator, and usually
registered users are glad to help us from time to time, or maybe even carding groups can release a valid serial we would use to create a generator.
The only scheme that would deny crackers to make generators, even if in possession of a valid key is public-key cryptography, such as well implemented
RSA. The other thing you can do is leaving some parts of the keyfile unchecked in current version, and each time a generator is released, add new checks to
render it useless, without changing the version number. I think the latest is rather a temporary solution, but can turn many crackers mad

The mind boggles...

[This message has been edited by Wayne Diamond (edited August 01, 2001).]

IP: Logged

Tom Hanlin
Member
posted August 01, 2001 09:38 AM     Click Here to See the Profile for Tom Hanlin     Edit/Delete Message   Reply w/Quote
As I recall it, "symmetric" does not mean that the same key is used both for
encryption and decryption, but that the same algorithm can be used both for
encryption and decryption-- that is, if

encoded$ = encrypt$(plaintext$, password$)

Then

plaintext$ = encrypt$(encoded$, password$)

...but possibly there are other meanings for the term.

It is not really possible to make a key-protected program that can't be broken.
The whole point of the computer is that it is a manipulator of data, and a
program is nothing more than data. Your program is constrained to be in a form
that the computer can run-- so, it is fundamentally unprotected. Breaking any
encryption or protection may take work, but it can't be prevented. The best you
can hope for is to make it a nuisance, or provide other forms of "value added"
that a user won't get with a pirated copy.

------------------
Tom Hanlin
PowerBASIC Staff

IP: Logged

Wayne Diamond
Member
posted August 01, 2001 10:14 AM     Click Here to See the Profile for Wayne Diamond     Edit/Delete Message   Reply w/Quote
Tom, very true, but the more time it takes them to crack it the better so personally im willing to spend a few days implementing protection into my program, it buys time and narrows down the type of people who can crack it to the eliteists and thats good enough for me . You're dead right though, and to be honest with you Im not sure if there's anything that these guys couldnt crack. In a way I have to admire them for that, it's a true talent - until last week my definition of 'reversing' was putting cold pizza in a microwave.

Timm, your algorithm (and all variations i could think of in my head) can all be cracked simply by reversing the algorithm. The private key would also be a reverse of the public key, so if private key is 12345, the public key would be 54321, regardless of how you implement the algorithm, so from that I'd assume that, upon realisation that the algorithm is assymetric or whatever you want to call it, first they'd try reversing the algorithm and trying that, before trying any other more complicated methods... so your code could possibly be described as pseudo-assymetric?
So, this is the challenge! Can you think of an algorithm that would use private and public keys that are of seemingly no relation? eg, 12345 and 59315
And, can that algorithm be directly reversed?
I'll admit to defeat already on this, as much as ciphers, cryptography and cryptanalysis fascinate me maths has never been my forte

------------------

IP: Logged

Tim Wisseman
unregistered
posted August 01, 2001 10:53 AM           Edit/Delete Message   Reply w/Quote
Okay, just a little bit more complex.

How about:
Public Key 125, 53
Private Key 78, 13

DIM sMess AS STRING
DIM iMess AS INTEGER
DIM a AS INTEGER
DIM b AS INTEGER
DIM i AS INTEGER

'// The message we are sending is just "h"
sMess = "h"
iMess = ASC(sMess)

'// Public Key = 125 and 53
a = 125
b = 53

a = 112 XOR a
b = 123 XOR b
i = iMess XOR a
i = (i + b) MOD 255
'// Your secret message
PRINT "Your secert message is: "; STR$(i)


'// Your incoming message is 179
iMess = 179

'// Private Key = 78 And 13
a = 78
b = 13

i = (i - a) MOD 255
i = i XOR b
sMess = CHR$(i)
PRINT "decoded message is: "; sMess


------------------

IP: Logged

Wayne Diamond
Member
posted August 01, 2001 11:08 AM     Click Here to See the Profile for Wayne Diamond     Edit/Delete Message   Reply w/Quote
*CH-CHING!* We have a winner!
So both the keys are unique and seemingly of no relation, AND the encryption and decryption routines are different and can't be reversed... I'm impressed!! Even more impressed that the code is still so relatively simple, even I can get my head around it
Thanks again so much for that Tim, that's pretty much exactly what I wanted to know, I'll be able to take the training wheels off and ride my own assymetric cipher now

------------------

IP: Logged

Tim Wisseman
unregistered
posted August 01, 2001 11:26 AM           Edit/Delete Message   Reply w/Quote
I have a reg code system that has kept the Russian
crackers confused for over 2 years now.

There is how the system works:

The user enters the reg code in to the program:

It looks something like this:

EE4R877 WZA3JUU GP86BYU 3RGDDYT TFEK8L7 19

To verify the reg code is good I have my program
convert the whole thing a series of longs using a
very complex set of math.

I then mask half the bits at random and use whats left and
feed it through a very complex hashing function that
has parts of its steps commented out depending on which
bits are being used and which bits are masked out.

The hashing code is stread out in over 20 places in my program in
the cores of important functions, the resulting values of the
hash are hidden in many odd places inside of important data
that the program is using.

In over 50 places the program does a quick check of the hash
value and sometimes does a bad bad thing if the value is not what is
expected. If it is SUNDAY it might crash the program with a devide by
zero error. . . It might pop up a message like, "Catch the Cows!".

The bottom line is you can not make a all powerful key generator
for my program using the EXE because only half the HASH algorithm
is compiled in any one release of the program. You can make a key
generator that will work for one release but it will break as
soon as a new version is released.

You can not crack an algorithm that was never
compiled into the code!

I have the added bonus of having my programs exchange data with
other users of the program, (interactive game). When one player
upgrades to the newer version of the game host program with a
different version of the hash, it will will detect all other in the
same game that are using fake keys by exchanging a hash value and
has the option of "zapping" them.

To date the only ones that have made fake keys have been
the Russians and the system is detecting them and stopping them
exactly as planned.

------------------

IP: Logged

Wayne Diamond
Member
posted August 01, 2001 11:53 AM     Click Here to See the Profile for Wayne Diamond     Edit/Delete Message   Reply w/Quote
Or we could get Semen to go around and beat them up? eg. Brute force
Thanks again Timm, Ive printed that out also for a re-read before I go to sleep, fascinating stuff - you're right about the part about crackers not being able to disassemble encrypted code, im looking into that also. (Time to get the dust off my flowchart program )

------------------

IP: Logged

Trevor Lane
Member
posted August 02, 2001 02:33 PM     Click Here to See the Profile for Trevor Lane     Edit/Delete Message   Reply w/Quote
None of those algo's really count as public key cryptographs. The
reason is that two things need to be made public. That is the Public
Keys and the algorythm that you want the other party to use to encrypt
the message.

Given the public keys and the encryption algorythm in the examples
given the decryption keys and decryption algorythm could be found
in a short amount of tme. (Minutes or at the very outsise hours)

PGP uses large prime factorials, due to the fact that it would take
many hundreds of years given current processing power to find the
private keys.

If you are interested in how they do it follow this link
http://pajhome.org.uk/crypt/rsa/rsa.html

regards
Trevor

------------------

IP: Logged

Rodney Wirtz
Member
posted August 02, 2001 11:25 PM     Click Here to See the Profile for Rodney Wirtz     Edit/Delete Message   Reply w/Quote
I recently read a book titled 'Hacker Attach!' by
Richard Mansfield.

In his book, he presented a private key system that encrypted
the plain text message using a random number generator.
If one wrote a program using PBCC random number generator,
I wonder if the code breakers using their decompilers could
'easily' decipher the random number generator code to obtain
the plain text message again?

Thank you to those that reply!

Rodney Wirtz

------------------

IP: Logged

Wayne Diamond
Member
posted August 02, 2001 11:40 PM     Click Here to See the Profile for Wayne Diamond     Edit/Delete Message   Reply w/Quote
Trevor, thanks for that link... it looks fairly straight-forward - you probably couldnt find a better page explaining it than that, but its still out of my league!
I challenge anyone to make a PB/CC version of that blokes example algorithm posted at that URL it seems to be a true PK crypt

------------------

IP: Logged


This topic is 2 pages long:   1  2 

All times are EasternTime (US)

next newest topic | next oldest topic

Administrative Options: Close Topic | Archive/Move | Delete Topic
Post New Topic  Post A Reply
Hop to:

Contact Us | PowerBASIC BASIC Compilers

Copyright © 1999-2005 PowerBASIC, Inc. All Rights Reserved.


Ultimate Bulletin Board 5.45c