Elizabeth did have a correspondence with the Ottomans in the last half of the sixteenth century. There was a recent popular history on this topic, The Sultan and the Queen by Jeremy Brotton, though I haven't had a chance to read it. A solid scholarly account is Lisa Jardine, "Gloriana Rules the Waves: Or the Advantage of Being Excommunicated" Transactions of the Royal Historical Society, (2004) pp. 209-222. It is a fascinating account, and certainly worth perusing. I believe the letter you are referring to was printed in Skilliter, William Harborne and the Trade with Turkey pp. 74-75. Skilliter writes that "her worship of the one true God, and her abhorrence of idolatry which brings her to overthrow images. She is appealing unmistakably to the basic religious tenents of her Islamic correspondents and separating herself from her Catholic neighbours."

Some of the letters between the Sultan and Elizabeth are printed in Hakluyt's Principal Navigations, though Skilliter finds some errors in translation, transcription and perhaps changes for Christian sensibilities. Here is the relevant volume, and the text itself starts on page 167.

As for the "protection" - what that meant was that the Sultan was guaranteeing protection for English Merchants, not necessarily Elizabeth herself. In 1579, the Sultan wrote Elizabeth promising "safe passage" to English merchants by land and sea to trade in his domains. England could export metals like tin and brass, which were used for cannon in the east. Their political discussion of making an alliance against the Spanish came later in the 1580s, as a result of the trade and correspondence of the previous years.