Nov 062013

Public Key cryptography solves one of the main problems with strong cryptography. How do you securely share the encryption/decryption key? If you have a secure channel for doing that, then why not use the same channel to send your plaintext message?

Public Key cryptography uses one key to encrypt and a different key to decrypt. This means you can share your Public Key with the world and anyone can use it to encrypt a message to you, but you are the only person with access to the Private Key to decrypt the message. Clever stuff!

This allows all sorts of exciting things – encryption, signing, non-repudiation and more.

But how does the maths behind this work? I’ve written a worked example below which shows a simplified version of how RSA encryption works. I’ve used small numbers so that you can follow along with a calculator, or a pencil and paper if you are cleverer than me!

Choose two random (large) prime numbers, p and q:
p = 13
q = 7

Multiply the numbers together to get the modulus, N, (the maximum value we can encrypt).
N = pq = 13*7 = 91  This is known as a trapdoor function – it’s easy to work out N if you know pq but very difficult to discover p and q if you only know N (for bigger numbers than we are using here)

Choose a public key, e.
e = 5 (generally chosen from {3, 5, 17, 257, 65537} which are also prime numbers)

To compute the associated private key, you need to know the two prime numbers (p and q). First compute φ (phi)
φ = (p-1)(q-1) =(13-1)(7-1) = 12*6 = 72

Then compute the private key, d.
d = (1/e) mod φ  or, written differently,  ed = 1 mod φ

In English, this means “find a whole number, d, which, when multiplied by ‘e’ and then divided by ‘φ’, leaves a remainder of 1” – there will be multiple values which are suitable.

Substituting the known values, we get
5d = 1 mod 72,  so d = 29  (because 5*29/72 = 2 remainder 1) or 461 (because 5*461/72 = 32 remainder 1) or 7373(because 5*7373/72 = 512 remainder 1) or other, larger, numbers…

We’ll choose the smallest number ’29’ here to make the calculations later a bit easier.

We now have all the required parts to encrypt and decrypt a message.

The public key which you share with the world is (N, e) = (N = 91, e =5)
The private key which is known only to you is (N, d) = (N = 91, d = 29)
The key pair is written ((N,e), d) – in our case ((91, 5), 29)

Before we can encrypt a message, we need to convert the message from letters to numbers. Lets use the standard Unicode Transformation Format 8-bit (UTF-8) encoding where each letter is represented by a number:

A = 65 G = 71 M = 77 S = 83 Y = 89
B = 66 H = 72 N = 78 T = 84 Z = 90
C = 67 I = 73 O = 79 U = 85
D = 68 J = 74 P = 80 V = 86
E = 69 K = 75 Q = 81 W = 87
F = 70 L = 76 R = 82 X = 88

– a space would be represented by 32

So, the message “ATTACK” would be encoded as 65, 84, 84, 65, 67, 75

To encrypt the plaintext message, m, into cypertext, c
c = me mod N
(remember, ‘e’ and ‘N’ are both public information)

A would be 655 mod 91 = 1,160,290,625 mod 91 = 39 (1,160,290,625 / 91 = 12,750,446 remainder 39)
T would be 845 mod 91   = 4,182,119,424 mod 91 = 28
C would be 675 mod 91   = 1,350,125,107 mod 91 = 58
K would be 755 mod 91   = 2,373,046,875 mod 91 = 17

Our encrypted message is now 39, 28, 28, 39, 58, 17

to decrypt the cyphertext, c, back to the plaintext, m
m = cd mod N
(remember, ‘d’ is only known to us!)

39 would be 3929 mod 91 = 1.3831637670618865315545398098597e+46 mod 91 = 65
28 would be 2829 mod 91 = 9.2807464717109449615203639109421e+41 mod 91 = 84
58 would be 5829 mod 91 = 1.37851600677743110483676343403e+51 mod 91 = 67
17 would be 1729 mod 91 = 4.8196857210675091509141182522307e+35 mod 91 = 75

3929 mod 91 is “the remainder when 39 multiplied by itself 29 times is divided by 91” – The numbers when we worked this out above become enormous – we can keep the numbers smaller by dividing by 91 and keeping just the remainder as we go along. If we do this one step at a time, we get:
1: 39*39 = 1,521 – this is bigger than N (91) so we can divide by 91 to get 16 remainder 65 (just keep the remainder!)
2: 65*39 = 2,535 – we can divide by 91 to get 27 remainder 78
3: 78*39 = 3,042 – we can divide by 91 to get 33 remainder 39
…and so on…
27: 65*39 mod 91 = 78
28: 78*39 mod 91 = 39
29: 39*39 mod 91 = 65  <— the same answer we got by doing 3929 mod 91

Our decrypted message, then, is 65, 84, 84, 65, 67, 75 which decodes to ATTACK using the UTF-8 table!

Let me know in the comments below if this makes sense and is useful…

Oct 302013

Certutil is a really useful tool for administering various parts of a Microsoft CA, but not all the switches are documented – they don’t even show up when you do a ‘certutil -v -?’ to show the full help.

So far, I have found the following verbs and options – the verbs have documentation if you specify them on the command line e.g. ‘certutil -setsmtpinfo -v -?’ I have only included the ‘hidden’ verbs and options below – you can find the standard options by checking the certutil help.

If you have any other verbs and options I’ve missed, please let me know in the comments and I’ll add them to this page. If you have any clever ways of using certutil, please let me know – I’m always looking for better ways of doing things!

Note: Microsoft may have hidden these options for a reason – use them with care, and at your own risk! Microsoft probably won’t provide support if you hit problems!

CertUtil [Options] -setsmtpinfo LogonName
Set SMTP info
[-config Machine\CAName] [-p Password]

CertUtil [Options] -getsmtpinfo
Get SMTP info
[-config Machine\CAName]

CertUtil [Options] -7f CertFile
Check certificate for 0x7f length encodings

CertUtil [Options] -Class [ClassId | ProgId | DllName | *]
Display COM registry information

CertUtil [Options] -CNGConfig
Display CNG Configuration

CertUtil [Options] -csptest [Algorithm]
Test CSPs installed on this machine
[-user] [-silent] [-csp Provider]

CertUtil [Options] -csplist [Algorithm]
List CSPs installed on this machine
[-user] [-silent] [-csp Provider]

CertUtil [Options] -delkey KeyContainerName
Delete named key container
[-user] [-silent] [-csp Provider]

CertUtil [Options] -key [KeyContainerName | -]
List key containers
[-user] [-silent] [-csp Provider]

CertUtil [Options] -SCDump [ReaderName]
Dump smart card file information
[-f] [-silent] [-split] [-p Password]

CertUtil [Options] -URL InFile | URL
Verify Certificate or CRL URLs
[-f] [-split]

CertUtil [Options] -SetCASites [SiteName]
Set Site Names for CAs
[-f] [-silent] [-config Machine\CAName] [-dc DCName]

CertUtil [Options] -SetCATemplates [+ | -]TemplateList
Set templates for CA

CertUtil [Options] -dsAddTemplate TemplateInfFile
Add DS Templates
[-dc DCName]

CertUtil [Options] -dsTemplate [Template]
Display DS Template Attributes
[-silent] [-dc DCName]

CertUtil [Options] -dsDeltaCRL [FullDSDN] | [CRLIndex [OutFile]]
Display DS Delta CRLs
[-enterprise] [-user] [-config Machine\CAName] [-dc DCName]

CertUtil [Options] -dsCRL [FullDSDN] | [CRLIndex [OutFile]]
Display DS CRLs
[-enterprise] [-user] [-config Machine\CAName] [-dc DCName]

CertUtil [Options] -dsCert [FullDSDN] | [CertId [OutFile]]
Display DS Certificates
[-enterprise] [-user] [-config Machine\CAName] [-dc DCName]

CertUtil [Options] -dsDel CN
Delete DS DNs
[-split] [-dc DCName]

CertUtil [Options] -ds [CN]
Display DS DNs
[-f] [-split] [-dc DCName]

CertUtil [Options] -getcert [ObjectId | ERA | KRA [CommonName]]
Select a certificate from a selection UI
[-silent] [-split]

CertUtil [Options] -enumstore [\\MachineName]
Enumerate certificate stores
MachineName — remote machine name.
[-enterprise] [-user] [-GroupPolicy]

CertUtil [Options] -exportPFX [CertificateStoreName] CertId PFXFile [Modifiers]
Export certificate and private key
CertificateStoreName — Certificate store name.  See -store.
CertId — Certificate or CRL match token.  See -store.
PFXFile — exported PFX data output file
Modifiers — Comma separated list of one or more of the following:
NoChain — Do not export the certificate chain
NoRoot — Do not export the root certificate
Defaults to personal machine store.
[-f] [-enterprise] [-user] [-GroupPolicy] [-split] [-p Password] [-t Timeout]

CertUtil [Options] -CAPropInfo
Display CA Property Type Information
[-config Machine\CAName]

CertUtil [Options] -getconfig3
Get configuration via ICertConfig

CertUtil [Options] -getconfig2
Get default configuration string via ICertGetConfig

Options: (I can’t find any info about what these do – some experimentation will be required!)