David Cameron has called for public support for new laws that bolster the online powers of police and intelligence agencies.
The Investigatory Powers Bill, to be published on Wednesday, covers which online tools are available to agencies that fight terrorism and digital crime.
However, opponents are concerned about the privacy implications of the new powers, which require internet firms to store records that will document communication made through apps and social media.
Sources close to the new bill said access to records will be strictly controlled and will not include a full browsing history or reveal every web page visited, although security services will retain the capacity to intercept the content of communications after obtaining a warrant.
Ministers have ruled out proposals to restrict encryption or ban it, despite fears in the intelligence community that advanced online security measures risk leaving them locked out of some areas of cyber space.
"At heart what this whole Investigatory Powers Bill is really about is actually something quite simple, because we all know when it comes to missing children or hideous crimes and the like we all know it's absolutely vital for the police to be able to know who called who and when," Cameron told ITV’s This Morning.
"Communications data - not the content of the call, that's governed separately - but the 'who called who and when', we do need to make sure that we can follow that online as well as through a telephone call."
In a call for public and political support for the new measures he said: "As Prime Minister I would just say to people, 'Please, let's not have a situation where we give terrorists, criminals, child abductors, safe spaces to communicate'.”
Whitehall sources have sought to distance the new legislation from the abandoned Communications Data Bill, which was labelled the "Snoopers' Charter" after it was drawn up in 2012, saying some of its "more contentious" tactics have been ruled out.