Okay, so look at this diagram.
There are two little boxes, that signify how a given profile should be signed.
In Phase 2, step 1, it says "Apple issued certificate", but it doesn't say which apple issued certificate (they issue more than one). I have tried my developer certificate and the MDM (APNS) certificate. It wasn't one of those. Is there a third magic certificate I somehow need (and how do I get it)?
In Phase 3, step 2, it says "Identity certificate", but again it's a little sketchy on the details. The only identity certificate I know of is installed on the device, using the device's private key, how is the server supposed to use that to sign a profile?
The only way I've gotten this to work, is by creating my own self-signed certificate, and pre-installing it on the device. Obviously this is not an elegant or particularly secure way to do things.
Follow up questions
My server certificate is issued by "DigiCert High Assurance EV Root CA" and is on the list: http://support.apple.com/kb/ht5012, but iOS 6 devices consider it "untrusted" when signing profiles, but just fine for SSL which is wierd. iOS 5 devices are fine though. Any idea why?
I don't really understand the encryption bit either. From the MDM documentation: "Each device must have a unique client identity certificate. You may deliver these certificates as PKCS#12 containers, or via SCEP. Using SCEP is recommended because the protocol ensures that the private key for the identity exists only on the device."
While I agree it is ultimately more secure that only the device itself knows its private key, it's somewhat problematic as a 2048-bit public key can only be used to encrypt about 100 bytes of data, which isn't enough for even the smallest possible payload.
Let me go over phase 2 and phase 3 first
In the Phase 2, step 1, iOS device will send to a server response which is signed by device certificate/key (each device comes with preinstalled certificate/key which is different for each device). These on device certificates/keys are issued by Apple.
On the server side, you should verify it using Apple Root Cetificate.
In the Phase 2, step 1-3 your profile service will send a SCEP request. This SCEP request contains information to let device know to which SCEP server it should talk. This SCEP server is your server. So, a device will talk to this SCEP server and will request new identity certificate from it.
In Phase 3, step 2 device response will be signed with certificate/key of this identity certificate. And now you should verify it with your Certificate authority root certificate. (One more note SCEP server in Phase 2 is kind-of proxy to yours Certificate authority)
And now answering your questions "MDM profile signining, which certificate to use?"
MDM profile could be encrypted and/or signed.
If you want to encrypt it, you encrypt it using identity certificate associated with this device. So, device which has a key for this identity, so it can decrypt it.
If you want to sign it, you sign with your server key. Device should have a server certificate installed, so it can verify signature.
BTW. On this subject. One thing which isn't shown on this diagram, but usually is requited - first step (before whole this enrollment) is usually installation of server certificate (for future profile signature verification). Potentially, you can skip this step if your server certificate is issued by well known CA (as example Verisign or something like that).
Let me know, if you have any followup questions. It took me a while to understand whole this OTA/MDM enrollment.
Update 1
I don't know why iOS 6 treat your certificate as untrusted for signing. I didn't work with certificates which were signed by well known CA's.
I have only one guess. It could be that between iOS 5 and iOS 6 they changed something regarding key chain. Generally speaking, each app has it's own key chain. And all well known certificates, I believe should be stored in Mobile Safari keychain. It could be that MDM/Preferences shared this keychain with MobileSafari in iOS 6 and now they don't share it. In such case, you will have to install this "DigiCert High Assurance EV Root CA" through a profile (to put it in correct keychain). However, it's wild guess.
Regarding encryption. First of all, you are right, if each device has it's own private key, it's way more secure. In such case, if anybody will steal a profile they won't be able to decrypt it (because only a device has a private key to do so). This is especially critically, if you are sending down profiles which are sensitive (as example, email account with both user name and password).
Very high level introduction into cryptography:
Any key (with any length) can encrypt data of any length. All encryption algorithms are designed that way that you can use the same key to encrypt any amount of data.
Asymmetric algorithms (like RSA) rarely used to encrypt data directly. In most cases, this algorithm is used to encrypt a key for symmetric algorithm (as example AES) and all following encryption/decryption is done using AES. There are two reasons for that: performance (AES is faster then RSA) and resources (AES is less resource hungry than RSA).
So, as result, if you need to encrypt profile you use PKCS7, which is internally uses RSA, AES (or other algorithms). Usually, you have a library to do this (OpenSSL or BouncyCastle). So, you don't have to figure out all these complexities.
BTW. If you have questions which aren't good fit for SO, you are welcome to contact me directly (my contact info in my profile).