Announcement

Collapse
No announcement yet.

Public key cryptography

Collapse
X
  • Filter
  • Time
  • Show
Clear All
new posts

  • Public key cryptography

    Code:
    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


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

  • #2
    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!
    Code:
    %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).]
    Rgds, Aldo

    Comment


    • #3
      I don't know if this falls under it or not, since it pretty much uses one key....

      Code:
      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
      Scott Turchin
      MCSE, MCP+I
      http://www.tngbbs.com
      ----------------------
      True Karate-do is this: that in daily life, one's mind and body be trained and developed in a spirit of humility; and that in critical times, one be devoted utterly to the cause of justice. -Gichin Funakoshi

      Comment


      • #4
        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).]

        Comment


        • #5
          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 -
          Code:
          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


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

          Comment


          • #6
            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)
            Code:
            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:
            Code:
            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).]
            -

            Comment


            • #7
              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

              Comment


              • #8
                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


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

                Comment


                • #9
                  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




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

                  Comment


                  • #10
                    *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


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

                    Comment


                    • #11
                      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.


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

                      Comment


                      • #12
                        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 )


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

                        Comment


                        • #13
                          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

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

                          Comment


                          • #14
                            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

                            ------------------
                            Rodney at Wirtz dot com

                            Comment


                            • #15
                              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


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

                              Comment


                              • #16
                                Wayne, it is true that crackers can't read encrypted code, but nor can the
                                computer run it. The code has to be decrypted before it will run, at which
                                point the cracker can read it too.

                                Rodney, the encryption approach you describe is not secure. As you note, a
                                "random number generator" (more accurately, pseudo-random number generator)
                                does not generate genuinely random number sequences.

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

                                Comment


                                • #17
                                  What I posted truely is public key encryption, however it is
                                  very easy to break and was just an example of how it is done.
                                  It was for learning purposes only and not something that could
                                  be used for real world work.

                                  Like my sample code, if you have a public key and the algoritms
                                  you can find the private key give enough time. It might take a
                                  nano second or 500 billion years, depending on the complexity
                                  of the system.

                                  The goal is to make the mathamatical path from the public key
                                  to the private key as hard as possible. That is the power of the
                                  RSA encryption methods.

                                  Tim

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

                                  Comment

                                  Working...
                                  X