Ticklish Techs

One of my DSLs uses many black connectors laying all over the screen. Every time I try to follow one connector I select it to change the border and to see a difference between all connectors. A colleague saw this design and asks me to implement a mouse over feedback for these connectors since all shapes have already such a visual feedback. The color of shapes changes a little bit if the mouse is over the shape. I had no idea how this should work for connectors…

First I take a look on the properties of the connector in the DSL designer and while searching I observed something: The DSL designer has this behavior on all connectors! I don’t have to write code for the MouseOver-event, but I have to figure out how to activate this behavior on my DSL editor.

For my surprise, the connectors on a newly created example language have a mouse over feedback, too. After playing around with some properties I was faced to a interesting fact: The mouse over feedback works pretty good for all connectors but black ones. I had no idea what’s going on.

Long story short: With Reflector I found one interesting method in the ShapeElement class: ModifyLuminosity(). The documentation is very clear:

"Calculates the luminosity of the highlight for the shape."

"The formula that creates luminosity. By default, the formula is: if luminosity is >= 160, then luminosity = luminosity * 0.9; otherwise, luminosity = luminosity + 40."

The luminosity of a black connector is 0 so the new luminosity will be 40. But for the color black you hardly see a difference between 0 and 40. But with this knowledge you can override the method in the connector class like this:

protected override int ModifyLuminosity
              (int currentLuminosity, DiagramClientView view)
{
  if(!view.HighlightedShapes.Contains(new DiagramItem(this)))
     return currentLuminosity;
        
 return 130;
}

The value 130 on a black connector works pretty good for me. Just try a few values und find a value you like.

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

Visual Studio 2005 had a known issue with the setup project and the RemovePreviousVersions option if the version number of your software is less than 1.0. This was a problem for me every time I released a new version of PhotoTagStudio. Like most small open source projects I won’t call it 1.0 (the current version is 0.7).

I described the problem and a workaround using the tool orca.exe. Every time I build a new setup I had to patch the setup. Last week I switched my PhotoTagStudio project to Visual Studio 2008 and created a new release. While patching the created msi I discovered that there is no need to do it that way any more. The problem seems to be fixed in the Visual Studio 2008 release!

Great work Microsoft!