gistfile1.cs

using System;
using System.Security.Cryptography;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            // The test values provided on http://wiki.vg/Protocol_Encryption are:
            // sha1(Notch) :  4ed1f46bbe04bc756bcb17c0c7ce3e4632f06a48
            // sha1(jeb_)  : -7c9d5b0044c130109a5d7b5fb5c317c02b4e28c1
            // sha1(simon) :  88e16a1019277b15d58faf0541e11910eb756f6

            // Hex digest generation
            Console.WriteLine("Notch: " + JavaHexDigest("Notch"));
            Console.WriteLine("jeb_: " + JavaHexDigest("jeb_"));
            Console.WriteLine("simon: " + JavaHexDigest("simon"));
            Console.ReadKey(true);
        }

        private static string JavaHexDigest(string data)
        {
            var sha1 = SHA1.Create();
            byte[] hash = sha1.ComputeHash(Encoding.UTF8.GetBytes(data));
            bool negative = (hash[0] & 0x80) == 0x80;
            if (negative) // check for negative hashes
                hash = TwosCompliment(hash);
            // Create the string and trim away the zeroes
            string digest = GetHexString(hash).TrimStart('0');
            if (negative)
                digest = "-" + digest;
            return digest;
        }

        private static string GetHexString(byte[] p)
        {
            string result = string.Empty;
            for (int i = 0; i < p.Length; i++)
                result += p[i].ToString("x2"); // Converts to hex string
            return result;
        }
        private static byte[] TwosCompliment(byte[] p) // little endian
        {
            int i;
            bool carry = true;
            for (i = p.Length - 1; i >= 0; i--)
            {
                p[i] = (byte)~p[i];
                if (carry)
                {
                    carry = p[i] == 0xFF;
                    p[i]++;
                }
            }
            return p;
        }
    }
}

Use:

result += p[i].ToString("x2");

This automatically adds the padding zero.

Wouldn't StringBuilder be a better option in GetHexString ?