Magerlin. The key is a drop from the Grand Shaman. It is required to give Magerlin one, for the first quest to get the magic skill.
There is a chance this key will break upon opening the gate, although the odds are unknown.
*If this happens while you are completing Magerlins first quest, you will have to find another key.