My iPhone was a locked one with 3.1.3 upgrade. I jailbroke it using redsn0w-0.9.4(windows). There is a trick at this step while start cracking firmware 3.1.3, you need to point 3.1.2(iPhone1,2_3.1.2_7D11_Restore.ipsw) firmware path to break 3.1.3(iPhone1,2_3.1.3_7E18_Restore.ipsw) while selecting firmware on first screen of redsn0w. This works just perfectly.
STEP 1: Jailbreak your iPhone 3.1.3 using redsn0w, and make sure you select