Great , accept the mission in Calm Lands , go to the Cavern of the Stolen Fayth , complete the "Tourist Trap" mission there and you'll receive the key if you pay 1 000 000 gil.
...just kidding , it will be yours for free
You can still do this mission in chapter 5 if you don't want to do it now. Hope you'll find this helpful! Take care