Ticklish Techs

It took me a lot of time to find a neat explanation of asymmetric encryption. Many sides say “a message is encrypted using a public key and it can only be decrypted with a corresponding private key.” Okay, fine, but how does it work in detail? Finally I found the RSA-entry in wikipedia. It’s almost what I was looking, but there are still lots of links to mathematical definitions and calculations you can’t do with your pocket calculator. So I decided to write a little compilation of the presented algorithm and to apply it using numbers you can handle. Also small number help to clarify things – but keep in mind that all the numbers are much much much greater in serious encryption.

How do we get our private-and-public-key-pair?

1. Choose two distinct (large) random prime numbers p and q
   p = 7,   q = 3.
   
2. Compute n = p*q. This n is used as the modulus for both the public and private keys
   n = 7*3 = 21.
3. Compute the totient: phi(n) = (p-1)(q-1)
   phi(21) = (7-1) * (3-1) = 12.
4. Choose an integer e such that 1<e<phi(n) and that e and phi(n) share no factors other than 1 (i.e. e and phi(n) are coprime.). e is released as the public key exponent.
   In order to chose an e I will factorize my phi(12) first: 12 = 2*2*3.
   I chose e=5. e does not necessarily have to be prime but it makes it easier to avoid sharing a factor.
5. Compute an integer d to satisfy the congruence relation d*e mod phi(n) = 1; d is kept as the private key exponent.
   “congruence relation” sounds more complicated than it actually is: Take two different numbers and apply the same modulo-operation to them (like mod 3). If the result is the same for both you may call your integers congruent modulo 5.  Like 11 and 16 are congruent modulo 5, since 11 mod 5 = 1 and 16 mod 5 = 1.
   So we are looking for a integer d that fits into
   d * 5  mod 12 = 1.
   I needed some tries here and wrote some lines to find the lowest d = 5. With one d found you can find all but just adding 12 :-). I didn’t want to take 5 as the private key exponent, since having the same exponent for encryption and decryption is… well… stupid. So I’ll choose 17.
   17 * 5 mod 12 = 1.
   85 mod 12 = 1.  Correct!

Do we have our private and our public key now? Yes, we have. Note that a key is not one single number but a pair of two numbers. Both are needed in the processes of encryption und decryption. One is the exponent and the other the modulus. Just a second and you’ll see why.

public key: e =5 (exponent) / n = 21 (modulus).

private key: d = 17 (exponent) / n = 21 (modulus). 

Let’s encrypt something

We have given our public key to anyone we know. And we kept our private key hidden somewhere under the bed. Now a beautiful and clever girl named Alice wants to send me a message. Fortunately the letters of her message can be represented as a stream of bits and we interpret this stream as a number. So her message is 10. It is important that her message is lower than our modulus, we’ll later see why. Let’s call her original message m and the encrypted message c.

m=10

The encryption it a simple formula: c = m^e mod n.

c = 10^5 mod 21

c = 100000 mod 21

c = 19.

So Alice hands me a little note saying “19”. 19? What the hack is that supposed to mean?

Now the magic happens

I rush back home to find my private key and apply it to “19”

The formula for the decryption look very similar: m = c^d mod n.

m = 19^17 mod 21.

m = 5480386857784802185939 mod 21. (Try it using calc.exe)

m = 10!

Wow! Alice says “10” to us. Isn’t 10 the international code for “I would like to date you?” I think so.

Signing

To encrypt with the public key means you can decrypt only with the private key. The converse is also true – to encrypt with the private key means you can decrypt only with the public key. Try it!

How can utilize this? We can use it to guarantee that a message is from a specific sender.

I have been dating Alice for some time now and we are used to leave messages to each other at a hidden place. Unfortunately another girl – Eve – is very jealous and has spied our secret mailbox. One week ago she found a message from Alice to me. She couldn’t read it, but she threw it away and replaced it by a mean offense against me. She encrypted it using my public key (which is public 🙂 ) and I thought it was written by Alice. The message started a little fight but luckily we found about Eve’s intention and started signing our messages. Now we transfer messages like this:

1. Alice writes me a message m.
2. She encrypts m using my public key, the result is c.
3. Now she encrypts c using her own private key, the result is cs (c signed)
4. She leaves me the message
5. I decrypt cs using her public key, getting c. (Eve can do this as well – but that’s it. She can’t read c and she can’t leave me a fake cs because she doesn’t have Alice’s private key.
6. I decrypt c using my private key and get back m – bingo!

Padding

Breaking this code (meaning “decrypt without having the private key”) is always a lot of work and hard trying. But is becomes much easier, when you know that m is short. That’s because you only have check that little fraction of configurations where m = c^d mod n leads to small ms. To avoid this small messages are artificially made longer until they are close to n. That process is called padding and even padding can be a tricky task.

Last question

We know what happens to short messages. But what happens to long messages? It is obvious that messages – seen as a number – can’t be greater than n-1, since the mod n – part of the decryption formula will never return values >n-1. I guess the message is split up in parts, but couldn’t find a satisfying answer. If I do, I’ll let you know.

Take care, 
Bob

Hi!

I just found a solution to a problem that was getting on my nerves for quite a time: I am using three computers, all WinXP Pro. They are all connected in one simple network and I don’t use much more than some folders to copy files from here to there. It worked fine for a long time but one day I couldn’t connect to anyone of the computers anymore. I am pretty sure I didn’t change a thing – it just happened. I browsed a lot (and I mean a lot) of websites that are dedicated to this problem. Most of them say (text copied from here):

1. Start the registry editor (e.g., regedit.exe).
2. Navigate to HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services \lanmanserver\parameters.
3. Double-click IRPStackSize (or if this registry setting does not exist, create it of type DWORD and ensure the case is correct).
4. Change the base to decimal, set the value to the default value for your OS, and click OK.
5. Reboot the computer or restart the “Server service”.

It did not work for me.

But I found the solution two minutes ago one on single German web site: When changing the value of IRPStackSize DON’T CHANGE TO DECIMAL. Change to (or leave it at) hex!.

Hex 30 (= Dec 48) was enough for me and after a reboot it worked again.

What a bug, MS, please fix it!

Here is a true story that happened to me six month ago:

My girl friend Grace wanted to go shopping and put me in the trunk, so I had to join her. We went to some discount supermarket (“Plus”) and she bought veggies, I bought meat, she bought tooth paste, I bought sweets. Then I stumbled about a nice offer: “400GB external USB-HDD for 99€” with a sticker saying “Samsung-HDD inside”. 99 was pretty cheap at that time and my experience with Samsung-HDDs is very good, so I put one in our shopping cart.

Back home I stored the meat and attached the new hdd to my laptop. Plopp – new drive found, drivers installed, everything cool. I did a format which went through quickly. “Here you are – congratulation to you new hard disc! – 3 GB ready to go.”

Uhm.. wait a moment. I didn’t expect 400, but something like 370GB found be fine. 3 GB is a little lesser than I expected. Hmm..

unattached it, attached it again – 3GB.

did another format – 3GB.

looked for a software or even a bios update for my laptop – up to date.

did some silly Google searched – nothing found.

tried another computer – 3GB.

Hmm… I started thinking… okay, let’s face it – 1 kb is officially reduced to 10byte, they just didn’t inform you.  Or maybe there is something wrong with the wires inside, a pin broken for the higher bytes or something. I fetched my mini screw driver and opened the case. Looked okay, the cable was clean and in place, the pins seemed  fine. There was a little table in a blue font giving numbers of sectors, cylinders and heads, but I couldn’t find any information on the size. Then I saw the brand: Maxtor. Maxtor? It was supposed to be a Samsung, wasn’t it? … What the heck?!? Suddenly the light of realization hit me very, very hard. I sat in silence for minutes – in deep disbelieve. It was sooo simple.

Some criminal had bought the original 400GB-HDD and replaced it with his (or her) old 3GB. Then he (or she) had taken it back to the shop, saying it wouldn’t work. He would get another one or his money back. Buy one – get one free. Bastard!

When I discovered this I felt like Monk and I was very excited. I went back to the shop, asked for the store manager (which was a friendly woman who looked like YarYar Binggs) and told her everything. Her reaction was very… well.. minimalistic and a little disappointing – all she did was to hand me a new hdd. (That one was 400GB)

Later I found I should have tried to recover some data from the 3GB-HDD, perhaps I could have helped to arrest a thief of 397GB but the good ideas are always late…

Have a good night and don’t let the bed bug bite you.

The start page of VS offers a list of the recent projects. It’s default length is 6, which is usually too short. I just found out that you can increase this length up to 24 in the Options\Enviroment\General-Tab.

.

I am happy.

Subversion is just the right thing for the small sized projects Benjamin and I do. We like it, put it’s not perfect and sometimes you find yourself in a deadlock like this one: Committing fails, because you need to update. Updating fails, because you database is corrupt and needs a clean-up. Cleaning-up fails, because there is lock on some files or folders from a previously failed action. Releasing the lock fails for any other reason.

After working with subversion (and the Tortoise-client) for a couple of years I know how to handle most problems, but last week I ran into an really persistent deadlock that drove me crazy. After almost two hours and finally attacking the problem with process-explorer, I found the cause: Copernic desktop search had locked a file inside a .svn – Folder, so it couldn’t be changed or deleted.

So be sure to have the "Indexing performance" of Copernic desktop search or similar tool switched off, when working with Subversion.

Today my world changed a little bit. My friend Rob asked me to write a fun application: You answer some questions and it tells you something, fairly simple. But he wanted to put it up his blog… oh-oh… Well… I am not much of a network- or server-guy and he runs a WordPress-blog on a hosted linux maschine, so .NET wouldn’t work. I started thinking about HTML-forms and java-script stuff but I don’t think it works too well with blog-posts and – by the way – I hate that sh*t, so I dropped it after one second.

Flash or Silverlight?

Then I thought about Flash and I guess that’s what you would use for a little game like that. But I don’t have it, I don’t want to buy it (is there a free version?) and I don’t have the time to learn it; although I think it’s pretty cool.

But… wait a moment? What about Silverlight? Isn’t it similar to Flash? I checked it out and I tell you: No, it’s not. Or nor yet. I downloaded the SDK, played a bit, read some pages. But… it’s just not the way you want it to be. Works only with java-script, isn’t easy, needs a lot of learning, doesn’t give you any moments of success. It’s just no fun.

Here comes GOA

So I complained in a chat with Benjamin. "Do I have to write a .NET-to-Flash-converter first?" He said: "There is one." – "WHAT?" – "Yes, I heard about something like that." and a minute later he produced a link to a product called "Goa Winforms". I could hardly believe my eyes. They claim to have an engine to compile .NET-Winform-Code to Flash (.swf) applications.

The basic version is free and comes as a 3MB installer, which integrates the tool smoothly into VS2005. After installing VS comes up with new project-types.

I choose the GOA Application and VS prepares a solution with a new project and a file that looks like a regular C#-file (the extension is .ccs by the way). Okay, let’s start it… Wow! A real Flash-application comes up. So far it’s just an empty form with one button – but it runs. It runs!!!

I think they implemented most of the common gui-components for flash and engineered a compiler that somehow converts C#-Code into an flash-interpretable format. Cool achievement!

Now, let’s design a fancy gui… but… were is the designer? In brief: There is none. You can’t design the gui as you usually would. Ouch. Okay, there is a solution to this ‘issue’, but it hurts and can’t be more than an temporary workaround: Add a Windows-application project to your solution, design your gui and copy the generated code to the GOA-application file.

Done? No. When you try to compile it, you get a bunch of errors and you have to manually delete any usages of properties that have been generated but are not supported by the GOA-version of the corresponding controls.

Now it works and you can continue to write your logic… but that takes us to another annoying point: The integration to Visual Studio could be improved a lot. Syntax-highlighting and intellisense work, but that’s it. Auto-re-indentation doesn’t work, errors and warnings do not all occur in the "Error-List"-Window, and my loved ReSharper didn’t recognize the code; but maybe that’s just because of the extension .css – is there a way to make ReSharper recognize those files as regular C#-files? Please let me know.

That’s was a lot of bleating, but lord don’t let me be misunderstood: It’s works and you get a lot for your effort; I had the fun application for Rob done in three hours (including learning, fighting, reading) and I am happy with it.

There is a lot more to play around with – like dymanic creation of controls – but it should be fine for the most purposes.

GOA vs. Silverlight

As soon as the GOA guys can get rid of the drawbacks, I think this approach has great potential. As long as Silverlight is ugly, "GOA Winforms" is something to really keep an eye on. And Silverlight 2.0 hasn’t proven yet that it can beat Flash. So, let’s see if Microsoft will take
the challenge.

Bonustrack

By the way.. here is the "application". It’s in German and doesn’t do much… but blame Rob for that 🙂

[kml_flashembed movie=”http://www.ticklishtechs.net/wp-content/uploads/2008/02/goaapplication1.swf” height=”270″ width=”350″ /]

Since there is not advertising on this blog, we just have to carry out our duty to officially inform you about the release of our first commercial software product 🙂 :

Arisan, an interface connecting the business process modelling software ARIS Toolset (by IDS Scheer) to .NET.

After almost 2 years of development we put up the  website www.arisan.de today.

A quite exciting moment and we hope for many downloads of the trial version. We are very confident in it’s technical quality and think Arisan is a very useful tool to work with ARIS in a sophisticated and professional way.

If you or one of your customers uses ARIS and if you are reading this blog because of it’s .NET content, you should give it a try.

Working on a private project we stumbled over an interesting behavior in the .NET sorting routines. There is a crucial difference between sorting (generic) lists of structs and sorting lists of objects.Take a look at this code:

(I am avoiding properties to shorten the example)

It’s a simple class that implements IComparable; Items are compared by the return value of the method GetSortkeystring. GetSortkeystring returns the variable ‘string sortkeystring’ and – if sortkeystring is null – initializes it with the .toString()-value of a random number that was to the constructor of the calls when creating the object.

Don’t look at the code too critical; it’s just the shortest code to illustrate the idea. In our real case the initialization of the sortkeystring is a very costly method that you wouldn’t want to call more often than absolutely necessary.

Now lets just get 100 random items und have them sorted.

What would you expect as output?

Before sorting. ctor_counter 100, getsortkey_counter 0
After sorting. ctor_counter 100, getsortkey_counter 100

Right. Now lets make a little change and turn the class into a struct.

What would you except as output now? The same as above? Dude, you are dead wrong!

Before sorting. ctor_counter 100, getsortkey_counter 0
After sorting. ctor_counter 100, getsortkey_counter 770!!!!!

Can you believe it? Neither couldn’t we and it took Benjamin a while to track it down. What is going on here? I didn’t know, so here is my first theory: The sortkeystring must be null again and again, since there is no other way to increase the getsortkeycounter. Doing the .Sort, .NET seems to create new instances of fancyitem all the time, which makes perfect sense: sortings objects is all about pushing around pointers, but structs are not "pointered at". So their real values have to be taken out of the list und put in at an other place in that list. But why does the value of sortkeystring get lost somewhere. A bug?

May I confuse you more?

Let’s try something else. In the example we initialized the sortkeystring as late as possible (lazy loading – remember. it’s a costly, costly method). But, come on, for the sorting we need each sortkeystring  anyway, so why no initializing it in the constructor?

The getsortkey_counter is gone, sortkeystring gets initialized in the constructor and GetSortkeystring() throws an exception if the value is lost.

The result was unexpected to me again. I was prepared for an exception, because we saw that the value gets lost. But no exception occurred.

Before sorting. ctor_counter 100.
After sorting. ctor_counter 100.
(and the list is still sorted properly)

What the hack is that supposed to mean? Let’s take a moment to sit down, have a drink and sum up the facts:

1. the constructor of the struct is officially called 100 times in all cases. Fine.
2. the GetSortkeystring()-method is called a lot. For each comparison. Fine.
3. in the first example the value of sortkeystring gets lost and has to be re-Initialized. Not fine but we have to take it.
4. in the second example the value of sortkeystring is initialized in the constructor and does not get lost. Fine, that’s what one would expect.

I really didn’t have no idea why 3 works so much different from 4. I played more and can add two more facts:

1. value types never get lost
2. reference types get lost like sortkeystring in the first example – as long as they are not initialized in the constructor.

Is there a kind of protection for variables, that are initialized in the constructor? I can’t believe that.

Last night in the bedroom…

…my girl-friend was already asleep, so I could mull this all over again… and was struck by the truth. Doh, it’s so simple:

As you know objects are called by reference (meaning "a pointer is passed") while structs are passed by value. Let’s say a passed struct lives as an independent copy of the original in the called method. Changes to this copy do not effect the original at all. Now List.Sort roughly works like this:

1. Find two elements to compare
2. Compare elements.
3. Switch their places if necessary

Whatever step 2 does, sooner or later it has to call

public int CompareTo(fancything other).

Ups… call by value. Now ‘other’ is of course just a copy and sortkeystring gets initialized in this copy – which does not affect the original in the list at all. And next time an original is compared… Do I have to say more?

This also explains, why variables, that have been initialized in the constructor, don’t get lost. Their values already live in the original – a pretty safe place to be in a struct world 🙂

Very satisfactory, I even don’t have to wake up my girl-friend! Good night, guys!

… I’m a man of wealth and taste. (Stones)

Yes, I am the new kid on the blog. Thanks to Benjamin for the first introduction. To introduce myself I tried to write a short version of my ‘computational biography’, but I ended up writing pages. If you really would like to read it, you will find the whole story here soon – with all comments and debug symbols. Now here is the compilied version:

Aged 33, I am living in the beautilful city of Düsseldorf (near Cologne) with my wonderful girl Grace. Thanks to my father I started programming 25years ago and couldn’t stop. In school I liked mathematics and languages, which was a strange but unique combination. Consequently (meaning ‘through wild twists in my personal life’ 🙂 ) I became a student of linguistics and quickly came to the field of computational linguistics. I graduated and after some more turbulences I started working for a nice company in Cologne. That’s where I first met Benjamin: The company was working on “java to .NET”-thing, Ben had already done the difficult tasks and I should type in some simple wrappings. I had learned C# like a week ago and felt dump like sh*t.
But I had time to improve and two year later we did the coolest project my working life so far: A converter from C#-Code to a special kind of process diagrams. I still like that tool a lot and realising it involved some of my major fields of interest like building parsers and pushing around graphs.
Since mid of 2006 I am a freelancer and currently I am working for a big German retail and logistics company.

I am interested in almost any subjects related to computers, except networking stuff :-). I am attracted most to games (boardgames as well, especially chess) and gaming theory, parsing, solving problems using graphs and .NET (of course).

My personal main task for 2008 is to lose some significant amounts of weight. I am not a fat guy, but during the last couple of years I gained the typical IT-belly.

I’ll come up soon with a nifty little post about comparing numbers. Stay tuned!

For my Software PhotoTagStudio I implemented a new feature to copy jpg-files from a memory card to the disk. I wanted to use that fancy Windows XP explorer copy dialog with the papers flying from one folder to another. And where I get the (more or less accurate) time estimation for free.

Searching the web I found the shell32.dll and the SHFileOperation function. This function does exactly what I need and on www.codeproject.com you can find a great article by arikp on how to address system32.dll from .net. arikp included sourcecode so you find everything you need to call the system32.dll functions from .net. Unfortunately two little features didn’t not work as expected:

hNameMappings is rarely used and can help only if I’m interesting in the new names the user had to give during the operation…

(but did not work in the ShellApi.cs)

…and finally lpszProgressTitle, If we set the flag FOF_SIMPLEPROGRESS, the progress dialog box does not present the file names and is supposed to present the text of this parameter. When I test this function I couldn’t get this parameter to show, it didn’t show the file names with the SIMPLEPROGRESS flag but it did not show the title parameter. What can I say, strange.

(did not work as well)

But I have to know the new names and thus had to get the NameMappings-thing working all by myself (I could not find a solution anywhere in the web). So I asked a good friend of mine, Wolfram Bernhardt, who subsequently did most of the following work:

He found a problem in the SHFILEOPSTRUCT:

[StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode)]
public struct SHFILEOPSTRUCT
{
    public IntPtr hwnd;
    public UInt32 wFunc;
    public IntPtr pFrom;
    public IntPtr pTo;
    public UInt16 fFlags;
    public Int32 fAnyOperationsAborted;
    public IntPtr hNameMappings;
    [MarshalAs(UnmanagedType.LPWStr)]
    public String lpszProgressTitle;
}


When marshalling this from .net to unsafe/native each element of the struct is stored at an address that is an multiple of 4. (This is the default for .net on Win32 for performance reasons). This leads to some unused bytes – i.e. fFlags is only 16 bit width and the next parameter should not leave a space of two byte.

The functions of shell32.dll are old fashion and do not waste any space. So they read wrong values after fFlags. The fAnyOperationsAborted wasn’t harmed that much and it’s value wasn’t checked too carefully in my application. But the hNameMappings-Pointer went totally wrong.

To change this behaviour you just have to add the Pack=2 parameter to the attribute:
[StructLayout(LayoutKind.Sequential, Pack = 2, CharSet = CharSet.Unicode)]

After this little change hNameMappings is marshalled back correctly and points to a mapping-structue. As a “side-effect” the lpszProgressTitle is now shown as expected – at least on Win XP, Vista seems to ignore this string. Obviously MS has changed this function of shell32.dll. But the more important functions work as desired.

To get the new filenames you have to set the Flags FOF_WANTMAPPINGHANDLE and FOF_RENAMEONCOLLISION. The latter allows the function to (automatically) rename files during copying. If a filename already exists, the new copy is renamed to something like “Copy of [filename]”. On a Windows Vista machine you don’t need the FOF_RENAMEONCOLLISION flag, because the user can choose the new option “Keep both the original file and the copyâ€? in the dialog that asks to override existing files. In both cases the hNameMappings is filled with a pointer to a list of Mapping objects that contain the original and the new filenames.

To get the list from the hNameMappings Pointer you have to implement two more structs and Wolfram did it, too. He added a new property NameMappings to the ShellFileOperation Class. (For details see the source code of the changes ShellLib.)

With the following download we provide an updated Version of the ShellLib with the described changes. For more information please refer to the original article on The Code Project and take a look on the demo code over there.

The enhanced ShellLib Code