Encrypt / Sign ? Not really sure


I need to put a small amount of inforamtion on a public server.
This information should be encoded so as to make it less than easily read by a human.
I need a program I write to be able to access this info and decrypt it.
This information needs to be checkable as having been created by me and not messed with by someone else.

I remember learning about Public-Private Key encryption at Uni (Some 8-10 years ago - it all made some kind of sense then.) I remember that once a private and public key are created, they act more or less like the ying and yang of each other.

Given an encryption algorithm, if you use 1 key to encrypt then the other is the key to the decryption.

So I thought I'd encrypt my data using my private key and then have my program decrypt it with my public key.

I found RSACryptoServiceProvider and set to work creating the following code:
Imports System
Imports System.Security.Cryptography
Imports System.Text
Public Class Cryptography
Private Shared mPublicKey As String
Private Shared mPrivateKey As String

' This function used only once to generate the Constants above
Public Shared Sub GenerateKeys()
Dim RSA As RSACryptoServiceProvider = New RSACryptoServiceProvider()
mPublicKey = RSA.ToXmlString(False) ' gets the public key
mPrivateKey = RSA.ToXmlString(True) ' gets the private key
End Sub

' This function should work but throws a runtime error talking about bad data
Public Shared Sub TestKeys()
Call GenerateKeys()
Dim StartString As String = "Hello EveryBody"
Debug.Print(String.Format("Start String:'{0}'", StartString))
Dim EncryptedString As String = EncryptString(StartString, mPrivateKey)
Dim EndString As String = DecryptString(EncryptedString, mPublicKey)
Debug.Print(String.Format("End String:'{0}'", EndString))
End Sub

' Utility Funcs
Private Shared Function EncryptString(ByVal StringToEncode As String, ByVal KeyInfo As String) As String
Dim RSAEncoder As New RSACryptoServiceProvider()
Dim DecodedBytes As Byte() = Encoding.Unicode.GetBytes(StringToEncode)
Dim EncodedBytes As Byte() = RSAEncoder.Encrypt(DecodedBytes, False)
Return Convert.ToBase64String(EncodedBytes)
End Function
Private Shared Function DecryptString(ByVal EncodedString As String, ByVal KeyInfo As String) As String
Dim RSADecoder As New RSACryptoServiceProvider()
Dim EncodedBytes As Byte() = Convert.FromBase64String(EncodedString)
Dim DecodedBytes As Byte() = RSADecoder.Decrypt(EncodedBytes, False)
Return Encoding.Unicode.GetString(DecodedBytes)
End Function
End Class

However I seem to get a "Bad Data" Cryptographic Exception

Can some one tell me where I'm going wrong?

Any help gratefully recieved.