After his release, Johnston was driven

to the home of Ismail Haniyeh,

the Palestinian prime minister,

in the Beach refugee camp in Gaza City

After discussions with Hamas officials,

he emerged with Mr Haniyeh, who held his hand aloft

Alan Johnston paid tribute to Hamas,

the Palestinian people and Palestinian journalists in particular.

"I could sense how much they were pressing for my release. Prime minister Ismail Haniyeh was very clear that I was a guest of the Palestinian people.

"I know the Hamas leadership put a huge amount of pressure on the kidnappers. If it had not been for that pressure then I might have been left in that room for a lot longer," he said.

Having staked its reputation on freeing Johnston, Hamas was keen to reap the political dividends from his release.

Mr Haniyeh presented Johnston with a scarf in Palestinian colours, a copper plaque of the Dome of the Rock and a Palestinian lapel badge.

Mahmoud Zahar, the Hamas foreign minister said Hamas security forces tracked Johnston as he was moved from house to house and were ready at any moment to rescue him.

He also said that Hamas was in control of the families of the kidnappers as an added means of imposing pressure in them.

Mr Zahar promised a new era in the Gaza Strip.

"Every kidnapping, every illegal behaviour, we will fight with all our force, the force of law, the force of moral principles. Every Palestinian and every foreigner will be secure and safe regardless of their political beliefs," he said.

Ayman Taha, the Hamas official who was in charge of negotiations, said his group had followed the wishes of the British government in not using force to free Johnston and added:

"We hope that this will lead to better relations with the British government in future."

The West's Appalling Attitude Towards Palestine

It may well be because Tony Blair has Palestine on his conscience that he took the thankless role of special envoy to that benighted land.

When we invaded Iraq, Blair made clear that reconciling Israel and Palestine was the twin challenge. His government failed to rise to it.

The road map to nowhere has been compounded by a lack of even-handedness, a want of political imagination and a subservience to Israel and the Bush administration.

That has directly contributed to the tragic shambles that is Palestine today. The old Israeli right-wing policy of perpetual divide and rule is again triumphant.

My third personal fact-finding visit to Palestine since 2003 ended a few weeks ago with a one-to-one meeting with Ismail Haniyeh, then Prime Minister.

Britain's refusal to engage with Hamas over its lack of democratic legitimacy is seen there as wholly cynical, given that the boycott continued after elections last year gave them more than 60 per cent of the legislative seats.

Blair will find the Palestinians feel bitterly about the West's failure to stop Israel building its illegal wall, its rapid colonisation of the West Bank and the humiliation of the checkpoint.

When I remarked to some Jewish NGO workers that the pass system seemed Kafkaesque, they said they called the West Bank 'Kafkastan'.

Israel's retention of £750m of Palestinian revenues and its wanton destruction of remaining Gaza infrastructure last year are further abuses over which we wring our hands.

The expanding colonisation, of course, gives the lie to Israel's 'security-first' policy, because it is the greatest provoker of Palestinian desperation.

None of this belittles or excuses Palestinian resistance. But even that is a two-way street. Israel kills, on average, at least four Palestinians - mostly civilians - for every one of its own killed by Palestinians.

I urged Haniyeh to deprive Israel and the US of their main justification for this oppression, namely Hamas's refusal to recognise Israel.

But he presides over a wide and vulnerable coalition beyond which are extremist groups, one of which held Alan Johnston.

Journalist Alan Johnston released after being held

captive in Gaza since March.

Alan Johnston, the BBC reporter held captive since March, described this morning how his kidnappers threatened to kill him and led him outside in handcuffs and a hood.

Speaking at the office of Ismail Haniyeh, the disputed Palestinian prime minister, Johnston told of his three-month ordeal at the hands of kidnappers who were "unpredictable and dangerous" and would be happy, he felt, to watch television as he died.

Johnston was freed just after 3am (23.00 GMT) following intense negotiations to avert a military confrontation between the forces of Hamas and his kidnappers, the Dogmush family, and their militia, the Army of Islam.

Yesterday, Hamas tightened their hold on the Dogmush family compound in the Sabra area of Gaza City and suggested they were prepared to launch a rescue attempt.

Late yesterday, there were renewed negotiations in which the Dogmush family was given an unspecified guarantee for their safety if they released the reporter.

After his release, Johnston was driven to the home of Mr Haniyeh in the Beach refugee camp in Gaza City. After discussions with Hamas officials, he emerged with Mr Haniyeh, who held his hand aloft. The pair then travelled to Mr Haniyeh's office where Johnston spoke of his captivity.

The reporter looked tired and drawn but spoke confidently as he thanked people for the support he had received and described the indifferent but sometimes brutal treatment at the hands of his captors.

"The last 16 weeks were by far the worst days of my life. It was like being buried alive, removed from the world. It was occasionally terrifying, with people who were both unpredictable and dangerous," he said.

"I dreamt about being free and then woke up to find myself in the same room. It's hard to believe even now that I will not wake up again in the same room."

Johnston told how his captors assured him they would not kill or torture him but then woke him up at 3am on his first night of captivity, handcuffed him, put a hood over his head and led him outside. "Then you wonder what's going to happen," he said.

On another occasion his captors became angry and chained Johnston by the wrists and ankles for 24 hours.

Johnston said that apart from the mental torture, his captors were rarely physically violent, though in the last 30 minutes he was roughly treated during his release.

"On the other hand, I had 16 weeks of solitary confinement in which they were often rude and unpleasant and they did threaten my life. For long periods of time they left me alone. It was really grim. I did not know how it would end," he said.

Johnston was allergic to the spicy Gazan food he was given and was ill twice until they gave him the plain food he asked for. Referring to those two periods, he said: "I felt they would be perfectly capable of watching television while I died."

Johnston was given a radio after two weeks of captivity and he described the joy at hearing of demonstrations for his release. "It was amazing to be lying in solitary confinement and hearing about demonstrations in Jakarta and Beijing," he said.

The mood of the captors changed when Hamas took control of the Gaza Strip last month.

"The kidnappers were most of the time comfortable and secure in their situation until Hamas took charge of the situation and then they became much more nervous. I began to feel that perhaps the end of my ordeal was in sight," he said.

After the Hamas takeover Johnston's captors initially talked about the possibility of killing him.

When Hamas increased their pressure, the kidnappers put an explosive belt on Johnston, which he described as the "real thing", and filmed him. Then they moved him to different buildings in the last five days.

He paid tribute to Hamas, the Palestinian people and Palestinian journalists in particular. "I could sense how much they were pressing for my release. Prime minister Ismail Haniyeh was very clear that I was a guest of the Palestinian people.

"I know the Hamas leadership put a huge amount of pressure on the kidnappers. If it had not been for that pressure then I might have been left in that room for a lot longer," he said.

Johnston said he was overjoyed but still surprised to be free. "It's hard to put into words what it is like to be free. Maybe you need to be imprisoned to realise how good it is to be able to phone your friends and walk on the street," he said.

Johnston said he was looking forward to being reunited with his family in Argyll, Scotland. His parents, Graham and Margaret, said they were overjoyed that he had been released.

Mr Johnston said: "The last 114 days I knew he had the strength and he would soldier on and seeing him now he looks fit and looks well. He is quite a bull."

The correspondent's father said the worst part of the kidnapping ordeal was the video that emerged of his son wearing an explosive device.

Now he was released, the family would be taking things slowly, Mr Johnston said.

"[Alan] has been incarcerated for all these months in solitary confinement so I think he should decompress a bit in private before we start opening bottles.

"He is not really a great party chap, and he is going to cringe when he realises there are pictures up all over the place. He is a pretty self-effacing chap and we will have a party, sure, but later on."

The reporter's mother said: "We are over the moon of course. We never did lose hope and I just always imagined him coming out."

Having staked its reputation on freeing Johnston, Hamas was keen to reap the political dividends from his release. Mr Haniyeh presented Johnston with a scarf in Palestinian colours, a copper plaque of the Dome of the Rock and a Palestinian lapel badge.

Mahmoud Zahar, the Hamas foreign minister said Hamas security forces tracked Johnston as he was moved from house to house and were ready at any moment to rescue him. He also said that Hamas was in control of the families of the kidnappers as an added means of imposing pressure in them.

Mr Zahar promised a new era in the Gaza Strip. "Every kidnapping, every illegal behaviour, we will fight with all our force, the force of law, the force of moral principles. Every Palestinian and every foreigner will be secure and safe regardless of their political beliefs," he said.

Ayman Taha, the Hamas official who was in charge of negotiations, said his group had followed the wishes of the British government in not using force to free Johnston and added: "We hope that this will lead to better relations with the British government in future."

Conal Urquhart @ Guardian